A counterexample to Hadwiger's conjecture

Introduction

For a finite graph $G$, write $\alpha(G)$, $\chi(G)$, and $h(G)$ for its independence number, chromatic number, and Hadwiger number. Thus $h(G)$ is the largest $t$ for which $G$ contains a $K_t$ minor.

Hadwiger’s conjecture, formulated in 1943 [16], asserts that $h(G) \ge\chi(G)$ for every finite nonempty simple graph $G$. We disprove it using graphs of independence number at most two.

Two disjoint edges are touching if an edge joins their endpoint sets. A connected matching is a matching whose edges are pairwise touching; write $\operatorname{cm}(G)$ for its maximum size. The word connected in this definition requires adjacency of every pair of matching edges.

Our main result is the following.

Theorem 1.1. There are arbitrarily large integers $m$ for which an $m$-vertex finite simple graph $G$ satisfies

A complete minor with many singleton or two-vertex branch sets gives a large connected matching. The precise counting inequality, proved in Proposition 3.5, is

Every color class has size at most $\alpha(G)$, so $\chi(G) \ge\lvert V(G)\rvert/\alpha(G)$. The same lower bound holds for fractional coloring, giving a second consequence of the construction. For a finite nonempty simple graph $G$, let $\mathcal{I}(G)$ be the family of its independent vertex sets. A fractional coloring assigns a nonnegative real weight $w_I$ to every $I \in\mathcal{I}(G)$ such that $\sum_{I \ni v} w_I \ge1$ for every vertex $v$. The ordinary fractional chromatic number $\chi_f(G)$ is the minimum of $\sum_I w_I$ over these assignments. An ordinary coloring gives a fractional coloring with unit weights on its color classes, so $\chi_f(G) \le\chi(G)$.

Corollary 1.2. There are finite nonempty simple graphs $G$ of arbitrarily large order $m$ for which

Thus Hadwiger’s conjecture and its fractional-coloring weakening $\chi_f(G) \le h(G)$ are false.

Proof. Summing the vertex constraints of any fractional coloring gives

Hence $\chi_f(G) \ge\lvert V(G)\rvert/\alpha(G)$. Apply Theorem 1.1 and the minor bound above, noting that $26m/75 + 2/3 < m/2$ for $m \ge5$. □

Reed and Seymour [26] discussed the weakening that, for every positive integer $p$, a graph with no $K_{p+1}$ minor should have a fractional $p$-coloring, and proved the corresponding $2p$-bound in their result (1.3). Their convention uses nonnegative rational weights, coverage exactly one at each vertex, and total weight at most $p$, so every such coloring is admissible above. Taking $p = h(G)$ in the corollary therefore disproves this prediction as well. The relaxation is on the coloring side; $h(G)$ remains the ordinary clique-minor number.

Historical context

Hadwiger’s conjecture places planar coloring in a broader minor-theoretic setting. The $K_4$-minor-free case was proved independently by Hadwiger [16] and Dirac [10]. Wagner’s structure theorem [30] makes the four-colorability of graphs without a $K_5$ minor equivalent to the Four-Color Theorem, proved by Appel and Haken, with Koch contributing to the reducibility part [1, 2]. Robertson, Seymour, and Thomas [27] proved that every graph without a $K_6$ minor is five-colorable, by reducing the obstruction to a graph that becomes planar after one vertex is removed. These results explain the conjecture’s link between coloring and the structure of minor-closed classes.

For general $t$, the density bounds of Kostochka [18] and Thomason [29] give $O(t\sqrt{\log t})$-colorability for graphs with no $K_t$ minor. Norin, Postle, and Song [23], Theorem 1.4 broke this degeneracy barrier, obtaining $O\left(t(\log t)^\beta\right)$ colors for every fixed $\beta> 1/4$. Delcourt and Postle [9], Theorem 1.5 reduced the bound to $O(t\log\log t)$. A recent preprint of Liu and Luo [21], Theorem 1.1 further gives $O(t\log\log\log t)$-colorability.

The restriction of Hadwiger’s conjecture to graphs of independence number at most two has an equivalent formulation: every such graph on $m$ vertices should have a $K_{\lceil m/2\rceil}$ minor. Plummer, Stiebitz, and Toft [25], Theorem 3.1 proved equivalence between the restricted conjecture and this universally quantified minor assertion. This identifies the case $\alpha(G) \le2$ as a setting in which chromatic number can be replaced by an explicit fraction of the order.

Duchet and Meyniel [11] proved the general lower bound $h(G) \ge|V(G)|/(2\alpha(G)-1)$, giving $h(G) \ge m/3$ when $\alpha(G) = 2$. Blasiak [3] obtained complete-minor models of order $\Omega(m^{4/5})$ using only singleton and edge branch sets. Fox [13], Theorem 2 strengthened the $m/3$ bound to

for an absolute constant $c > 0$. His Theorem 3 also yields a connected matching of size $\Omega(m^{4/5}(\log m)^{1/5})$, since its alternative clique of the same order can be paired. These bounds describe the quantitative background to the fixed linear upper bounds in Theorem 1.1 and Corollary 1.2.

Füredi, Gyárfás, and Simonyi [15] proposed the sharp connected-matching conjecture: a graph with independence number two and order $4t-1$ has a connected matching of size $t$. They verified the assertion through $t = 17$, and Chen and Deng [5] extended this range to $t = 22$. Cambie [4], Theorem 1.5 proved that Hadwiger’s conjecture implies this statement. The graphs in Theorem 1.1 also disprove the sharp connected-matching conjecture: delete at most three vertices to obtain order $4t-1$; the connected-matching number does not increase and remains below $t$ for sufficiently large orders. The remaining graph has independence number exactly two, since a complete graph of order $4t-1$ has a connected matching of size $2t-1$.

Substantial positive results also come from additional clique structure. Chudnovsky and Seymour [6], Theorem 1.3 proved that an $m$-vertex graph with independence number at most two has a $K_{\lfloor m/2\rfloor}$ minor whenever its clique number is at least $m/4$ for even $m$, or at least $(m+3)/4$ for odd $m$. Their method packs induced three-vertex paths. Norin and Seymour [22], Theorem 1.2 subsequently combined this structure with random pairing to obtain minors of order $\chi(G)$ and edge density at least $\gamma-o(1)$, where $\gamma= 0.986882\ldots$ is a fixed constant. These results highlight the requirement in a complete-minor model: every pair of branch sets must be joined, whereas high density permits missing adjacencies.

A weaker conjecture asks only for some absolute $c_0 > 0$ such that $\operatorname{cm}(G) \ge c_0|V(G)|$ for all sufficiently large graphs with $\alpha(G) \le2$ [15]. Yip [31], Theorem 7 proved a dense variant: a matching of linear size can have the proportion of its non-touching edge pairs made arbitrarily small, with the linear coefficient depending on the prescribed proportion. That statement allows such pairs to remain. The fixed coefficient in Theorem 1.1 leaves the weaker conjecture for smaller positive coefficients unresolved; it does not assert $\operatorname{cm}(G) = o(\lvert V(G)\rvert)$.

A related parity-constrained problem has a different recent resolution. An odd $K_t$ minor consists of $t$ disjoint trees, each properly two-colored, with a same-color edge joining every pair of trees. Kühn, Sauermann, Steiner, and Wigderson [19] disproved the odd Hadwiger conjecture using graphs of independence number at most two. The construction in this paper bounds the order of ordinary complete minors.

The separate companion manuscript [24], Theorem 1.1 constructs graphs with $\chi(G) > \mu(G) + 1$, where $\mu$ is the ordinary Colin de Verdière invariant. Since $h(G) \le\mu(G) + 1$, its result also gives counterexamples to Hadwiger’s inequality. The argument here proves the connected-matching bound directly and does not use that invariant.

The construction and its proof

We build $G$ by sampling from a finite probability space and declaring some pairs to be holes, or missing edges. The hole relation has no loops or triangles. Its complement on the sampled positions therefore has independence number at most two, even when sampled elements repeat. An ordered pair with no internal hole is called a unit; it represents a possible matching edge. Two units conflict when all four cross pairs are holes, as in Figure 1. Such edges cannot belong to one connected matching.

The main distribution theorem forces conflicts between independent units drawn from any law with specified marginal and joint density bounds. It permits arbitrary dependence between the endpoints of a unit, as is necessary when the units come from a matching. An entropy-minimizing container argument transfers this statement to the finite sample: while a family of units supports such a law, supersaturation supplies a conflict neighborhood to delete; when no such law remains, a capacitated cut covers the residual family by a small set of endpoint types and a small set of pairs.

To define holes, each sampled configuration carries injective linear maps into common binary vector spaces. The coefficient spaces record monomial evaluations $v$ at Boolean points; their point moments are the rank-one matrices $vv^{\mathsf{T}}$. The frame maps induce an embedding $U_o$ of a space built from these moments, together with a linear functional $u_o$ on the ambient tensor space. Auxiliary frame columns will be used to impose the cross-contraction equations. A hole is certified by a shared tensor and two prescribed identities for the cross contractions. The identities come from a symmetric bilinear form; summing them around a hypothetical triangle cancels every bilinear term and leaves 0 = 1. Section 2 proves this parity mechanism before constructing the particular moments and frames.

Forcing four holes is the harder task. The construction has one unbounded parameter $n$, and the ambient vector dimension is $N = M_0 n$, with $M_0$ fixed before the limit. The three main steps are as follows.

1. Finite certificates for four holes (Sections 5 to 7). The candidate witnesses are short sums of point moments. A point’s key is the tuple of its images under the relevant frame maps; equal keys on the two sides give a shared tensor. We retain specified images of a bounded number of coefficient directions, called pins. A fixed Boolean selector labels the points; interpolation and a bounded set of excluded labels make the key directions independent modulo these pins. A separate low-rank moment decomposition identifies the obstructions to solving the cross-contraction equations. Once the corresponding scalar conditions hold, the remaining equations cost only $O(n)$ bits. The collision criterion in Proposition 7.1 reduces four holes to overlap of the accepted key distributions. The witness sums use paired lists of points, and a scalar recipe prescribes their scalar conditions. Sampling the point parameters with the configuration fixed will be called a query; its full key is the list of the point keys.

2. Preparation of the unit law (Sections 8 and 9). Conditioning on exact pin images decomposes the law into parts called leaves, with control of every further independent image prescription. A small table records the cross pairings of the projected pin directions and the auxiliary frame directions. The scalar conditions must be compatible with this table. Phase estimates produce compatible tables on a positive mass of independent unit pairs, or on a smaller mass at least a fixed multiple of $N^{-4}$ determined by their leaves.

3. Forcing overlap (Sections 10 to 14). Each leaf’s accepted key distributions have finite $L^1$ approximating families. Estimates for the mixed law also control tests of single keys and the scalar values recorded with them. A product comparison connects these single-position estimates to tests of the full key tuple. If overlap vanished in the positive-mass case, a common limit would rule out every scalar recipe whose matched positions have positive overlap; finite-dimensional duality produces precisely such a recipe. The inverse-polynomial compatibility mass may disappear in this limit, so it is handled separately: a uniform large-set estimate is applied to a finite family chosen on one leaf before the independent opposite leaf is sampled.

The Boolean moment argument uses commuting multiplication operators, as in the flat-extension approach to moment problems [20]. The distribution-to-graph argument combines information projection [8], independent-set fingerprints [17, 28], and a capacitated cut [12]. The overlap estimates use entropy [7] and the energy-increment method of weak regularity [14]; the additional constraints from the frame pairings are retained explicitly in their proofs.

Organization and conventions

Sections 2 and 3 define the frames and holes and reduce the graph problem to uniform supersaturation. Section 4 establishes the frame-image estimates and the decomposition into pinned leaves. Sections 5 to 7 prove the algebraic realization and collision criteria. Sections 8 and 9 prepare the unit law and its small tables. The analytic comparison tools are established in Sections 10 and 11. Sections 12 and 13 prove overlap on the branches with positive limiting compatibility mass, and Section 14 handles the remaining branch and completes the proof. Appendix A collects the order of choices and the quantitative margins.

All vector spaces, matrices, ranks, and algebraic forms are over $\mathbb{F}_2$. Probabilities, densities, norms, and entropies are real. Logarithms in bit counts have base two; changing the base for entropy only changes fixed constants. Constants described as bounded may be very large but are independent of $n$. An $O(n)$ scalar record has its coefficient fixed before $M_0$ is chosen. Later fixed test accuracies and partition sizes may change how large $n$ must be; they do not change the construction.

The two endpoints in one unit may be dependent. Separate units, and their leaves before additional pairing conditions, are sampled independently. Query subdensities retain the mass lost to all acceptance tests.

The hole relation and its tensor realization

The construction has two tasks. Its missing-edge relation must be triangle-free, so that the resulting graph has independence number at most two. It must also provide enough missing edges to prevent a large connected matching. We first give the algebraic reason for triangle-freeness. The tensor and frame construction that follows provides the additional structure needed for the second task.

A triangle-free relation

Let $\mathcal{X}$ and $\mathcal{V}$ be finite-dimensional vector spaces over $\mathbb{F}_2$. Fix a linear functional $a \in\mathcal{X}^*$ and a symmetric bilinear form $T$ on $\mathcal{X}$, and write

Let $\Omega$ be a finite set. For each $i \in\Omega$, suppose we have an injective linear map $U_i:\mathcal{X}\to\mathcal{V}$ and a linear functional $u_i \in\mathcal{V}^*$.

Definition 2.1. Two elements $i,j \in\Omega$ have a hole between them if there exist $\lambda_i,\lambda_j \in\mathcal{X}$ such that

The middle two identities are identities of linear functionals on the whole space $\mathcal{X}$.

Thus a hole has a shared vector in $\mathcal{V}$, one witness for it in each copy of $\mathcal{X}$, and opposite values of $a$ on the witnesses. The functional identities make these requirements incompatible around a triangle.

Lemma 2.2. The hole relation is symmetric, has no loops, and is triangle-free.

Proof. Symmetry follows by interchanging the endpoints. A loop would have $U_i\lambda_i=U_i\lambda_j$, hence $\lambda_i=\lambda_j$ by injectivity, contradicting the last equation of (1).

Suppose that three distinct elements have holes on all three pairs. For a directed incidence $ij$, let $x_{ij}$ be its witness at $i$. For distinct $i,j,k$, evaluate the functional identity for $ij$ on $x_{ik}$:

Sum over the six ordered choices of $(i,j,k)$. For fixed $j$, the two arguments on the left are equal by the sharing equation for the remaining edge $ik$, so they cancel. For fixed $i$, the two bilinear terms cancel by symmetry of $T$. The remaining sum is

a contradiction.