Matchings and Hadwigerʹs Conjecture Original Research Article

Assuming that a graph G on n vertices is a minimal counterexample to Hadwigerʹs Conjecture χ(G)⩽η(G), we apply the Edmonds–Gallai Structure Theorem to its complement, H, to find that H has a matching of size ⌊n/2⌋. Hence Magyar Tud. Acad. Mat. Kutató Int. Kőzl. 8 (1963) 373: χ(G)⩽⌈n/2⌉. Further, H is homeomorphic to a three-connected graph, and is of tree width at least four. The same holds for a minimal counterexample G to Colin de Verdièreʹs Conjecture μ(G)+1⩾χ(G).