we-solve (beta)

Math-63 · mathematics · Graph theory

Hadwiger Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

A graph minor is obtained by vertex deletions, edge deletions, and edge contractions. A proper $t$-coloring is a map $c:V(G)\to\{1,\ldots,t\}$ with different colors at adjacent vertices. Hadwiger's assertion is \[ K_{t+1}\not\preccurlyeq G\quad\Longrightarrow\quad\chi(G)\le t \] for every finite simple graph $G$ and every $t\ge1$. The complete graph is excluded as a minor, not merely as a subgraph or an induced subgraph.

Formulation and concept references: [S1].

Short English statement

If a graph cannot contain a complete graph of order $t+1$ even after contractions, must $t$ colors suffice?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-63-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-63

Chromatic number beyond clique-minor size: The claimed graphs have h(G)<chi_f(G)<=chi(G), directly violating Hadwiger’s ordinary minor-coloring implication.

Colin de Verdière chromatic obstruction: The claimed graphs have h(G)<chi_f(G)<=chi(G), directly violating Hadwiger’s ordinary minor-coloring implication.

Linear list-coloring in clique-minor size: The claimed list-coloring estimate implies chi(G)<=C h(G), a weaker constant-factor bound than Hadwiger’s required factor one.

The claimed counterexample lies within the question’s hypotheses and contradicts its universal conclusion.

Hadwiger Conjecture

OpenAI's claim

Chromatic number beyond clique-minor size: The counterexample paper claims arbitrarily large finite graphs with $\chi_f(G)>h(G)$, hence also $\chi(G)>h(G)$; no independent vertex set in an example contains three vertices.

Colin de Verdière chromatic obstruction: The manuscript claims finite graphs whose fractional chromatic number is greater than $\mu(G)+1$, and therefore whose ordinary chromatic number violates the same bound; such examples exist at arbitrarily large orders.

Linear list-coloring in clique-minor size: The paper claims a universal constant $C$ with $\chi_{\mathrm{list}}(G)\le C h(G)$ for every finite nonempty graph; the factor is independent of the graph and its order.

Mathematical statement of the claimed result

Mathematical claim 1.
There are finite simple graphs $G$ of arbitrarily large order $m$ with independence number $\alpha(G)\le2$ and maximum size of a pairwise-touching matching less than $m/100$. The resulting corollary states \[h(G)<26m/75+2/3<m/2\le\chi_f(G)\le\chi(G),\] where $h(G)=\max\{t:K_t\text{ is a minor of }G\}$ and $\chi_f,\chi$ are fractional and ordinary chromatic numbers. Thus the exact inequalities $\chi\le h$ and $\chi_f\le h$ fail; no conclusion about replacing $h$ by a fractional minor parameter is supplied.
Mathematical claim 2.
The claimed counterexamples are finite simple graphs of arbitrarily large order $m$ with \[\alpha(G)\le2,\qquad\mu(G)+1<m/2\le\chi(G),\] where $\mu(G)$ is the Colin de Verdière spectral graph invariant. The fractional-coloring corollary strengthens the obstruction to \[\chi_f(G)\ge m/\alpha(G)\ge m/2>\kappa(G)+1\ge\mu(G)+1\ge h(G).\] Here $\kappa$ is its strong-Arnold-property-free spectral relaxation, and $h$ is the largest complete-minor order. In particular both $\chi\le\mu+1$ and $\chi_f\le h$ are refuted. A further corollary gives $\chi_{\mathrm{list}}(G)\le C(\mu(G)+1)$ with an absolute $C$.
Mathematical claim 3.
For every finite nonempty simple graph $G$ there is an absolute integer $C\ge1$, independent of $G$, such that \[\chi_{\mathrm{list}}(G)\le C h(G),\qquad h(G)=\max\{t:K_t\text{ is a minor of }G\}.\] The list chromatic number is the least $k$ for which every assignment of $k$ available colors per vertex permits a proper coloring. Consequently $\chi(G)\le Ch(G)$. The constant-factor bound does not imply the conjectured coefficient $1$.

Outline of the argument

Chromatic number beyond clique-minor size: The graph construction uses Boolean moment representations and paired frames to control compatible vertex distributions. Entropy projection, fingerprints for independent sets, and a capacitated-cut argument transfer the distributional constraints to finite graphs. The resulting obstruction limits clique-minor size, while the small independence number gives a larger fractional chromatic number.

Colin de Verdière chromatic obstruction: Allowed channel images are thinned while preserving the primal distribution, supplying enough compatible pairs for the conflict estimates. A Boolean moment argument restricts low-rank matrix representations. Entropy and finite sampling then produce graphs for which every well-signed matrix with a single negative eigenvalue has too much rank to support the proposed chromatic inequality.

Linear list-coloring in clique-minor size: For small minor-free graphs, a random global partition of colors gives each vertex many eligible bins. Stable-set sampling repeatedly reduces fractional chromatic complexity among eligible vertices. If the reduction failed, separator and connectivity arguments would assemble disjoint clique models into the excluded minor; the resulting small-graph bound feeds the global list-coloring argument.

Formal verification

Family 157 describes Lean coverage for the list-coloring upper bound with a universal multiple of clique-minor size; neither chromatic counterexample is part of this selection.

Chromatic number beyond clique-minor size: No manuscript-specific Comparator is listed in the pinned inventory.

The documented selection does not cover the entire manuscript assertion relevant here.

Colin de Verdière chromatic obstruction: No manuscript-specific Comparator is listed in the pinned inventory.

The documented selection does not cover the entire manuscript assertion relevant here.

Linear list-coloring in clique-minor size: The manuscript links ListHadwiger.lean.

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →

Math-63-A1 · No claim recorded · LLM-generated · gpt 6 astra pro ·

gpt 6 astra pro attempt on Math-63

Hadwiger Conjecture

Definitions and mathematical statement

A graph minor is obtained by vertex deletions, edge deletions, and edge contractions. A proper $t$-coloring is a map $c:V(G)\to\{1,\ldots,t\}$ with different colors at adjacent vertices. Hadwiger's assertion is \[ K_{t+1}\not\preccurlyeq G\quad\Longrightarrow\quad\chi(G)\le t \] for every finite simple graph $G$ and every $t\ge1$. The complete graph is excluded as a minor, not merely as a subgraph or an induced subgraph.

Formulation and concept references: [S1].

Short English statement

If a graph cannot contain a complete graph of order $t+1$ even after contractions, must $t$ colors suffice?

Research attempt

Current frontier.
Delcourt--Postle's established asymptotic colouring bound is $O(t\log\log t)$ for graphs excluding $K_t$ as a minor. Liu--Luo's September 2026 preprint states an improvement to $O(t\log\log\log t)$; this is a recent authors' theorem, not independently proof-audited here [E1]. Neither bound gives the exact $t-1$ required for $K_t$-minor-free graphs. Claims about the odd-minor variant in [S3] do not by themselves refute the ordinary minor assertion. The investigation below uses ordinary connected branch sets throughout.
Attack route.
A minimum counterexample would be vertex-critical and have strong degree constraints, but large degree alone does not force the required exact clique minor. Another route contracts a connected dominating set to create one branch set and inducts on the remaining graph. This gives an elementary known independence-number bound. The missing step for Hadwiger is then pinpointed as retention of enough chromatic number after removing such a set. The proof is worked out rather than presenting the weaker bound as the target.
Attempt: a connected dominating set with an independent witness.
For a connected nonempty graph $G$, write $\alpha=\alpha(G)$. Construct sets $I\subseteq D$ with $I$ independent, $D$ connected, and $|D|=2|I|-1$. Start with one vertex in both sets. If $D$ does not dominate $G$, connectedness supplies a vertex $y$ at distance exactly two from $D$, on a path $d,x,y$ with $d\in D$. Add $x,y$ to $D$ and $y$ to $I$. The new $D$ is connected, and $y$ has no neighbour in the old $D$, so the new $I$ stays independent. The stated size invariant persists. Since the graph is finite, the process stops at a connected dominating set with \begin{equation}\label{wsref-0-65-71-38-30-3a-64-6f-6d} |D|\leq2\alpha(G)-1. \end{equation} This is the elementary connected-domination mechanism behind the classical Duchet--Meyniel bound [E2]; it is reconstructed here without a novelty claim.

Let $h(G)$ be the maximum order of a complete minor. We now prove \begin{equation}\label{wsref-0-65-71-38-30-3a-77-65-61-6b} h(G)\geq\frac{|V(G)|}{2\alpha(G)-1} \end{equation} for every nonempty graph, by induction on its number of vertices. For disconnected graphs with nonempty components $G_j$, induction gives $h(G_j)\geq n_j/(2\alpha_j-1)$. Since $\alpha(G)=\sum_j\alpha_j$ and $h(G)=\max_jh(G_j)$, \[ h(G)\geq\frac{\sum_j n_j}{\sum_j(2\alpha_j-1)} \geq\frac{|V(G)|}{2\alpha(G)-1}. \] For connected $G$ choose $D$ from (eq80:dom). If $D=V(G)$, the right side of (eq80:weak) is at most one. Otherwise let $G_j$ be the components of $G-D$. Contract $D$ to one branch set. It is adjacent to every vertex outside it, hence to every branch set of any clique minor in any $G_j$. Thus \[ h(G)\geq1+\max_jh(G_j) \geq1+\frac{|V(G)|-|D|}{\sum_j(2\alpha(G_j)-1)} \geq1+\frac{|V(G)|-|D|}{2\alpha(G)-1}. \] The last quantity is at least the right side of (eq80:weak), by (eq80:dom). This completes the induction, with the empty remainder handled separately rather than dividing by an empty denominator.

Attempt: a precise chromatic-retention condition.
Suppose every connected graph of chromatic number $k\geq2$ possessed a connected dominating set $D$ with \begin{equation}\label{wsref-0-65-71-38-30-3a-6d-69-73-73-69-6e-67} \chi(G-D)\geq k-1. \end{equation} Then induction on the number of vertices would prove $h(G)\geq\chi(G)$: the smaller graph $G-D$ would have a $K_{k-1}$ minor, and contracting $D$ would supply the $k$th branch set. Disconnected graphs are handled by a component of maximum chromatic number. Thus (eq80:missing) is one explicit sufficient lemma for the full assertion, not something implied by (eq80:dom).

The converse direction need not be asserted. Hadwiger might hold by branch sets that cannot be arranged through this dominating-set induction. The condition is a proposed stronger structural route, and a counterexample to it would not itself refute Hadwiger.

There is nevertheless a rigorous minimum-counterexample consequence. If a smallest-vertex graph $G$ violates $h(G)\geq\chi(G)$, put $k=\chi(G)$. It is connected and vertex-critical: otherwise a smaller component or a vertex deletion has the same chromatic number, contradicting minimality. Hence its minimum degree is at least $k-1$, because a colouring of $G-v$ by $k-1$ colours would extend across a vertex of degree at most $k-2$. Moreover, every connected dominating set $D$ in this $G$ satisfies $\chi(G-D)\leq k-2$. Otherwise minimality and the contraction argument just given contradict $h(G)<k$. This is a concrete constraint a counterexample search can test, with no assumption that such a graph exists.

Stress test.
A bound on $|D|$ in terms of $\alpha(G)$ does not control the loss of chromatic number. The elementary inequality $\chi(G)\leq\chi(G[D])+\chi(G-D)$ loses as many colours as the induced subgraph on $D$ needs; connectedness does not make that number one. The independent witness $I\subset D$ constructed above certifies the size bound, not a colouring of all of $D$ with one colour. This is precisely the unproved leap that would turn (eq80:weak) into Hadwiger.

Kempe-chain ideas face a related issue: paths between colour classes may intersect each other. A clique minor needs disjoint connected branch sets, not merely a path for each desired pair. The connected dominating set solves disjointness for one branch set, but the retained chromatic number is then the obstacle. Large average degree, restricted forbidden subgraphs, or a bound with extra logarithmic factors do not supply the exact condition.

The companion script tests the construction (eq80:dom) on a finite collection of small connected graphs and verifies connectedness, domination, independence and the size identity after every step. It does not certify (eq80:missing) for all graphs or search all possible minors at unbounded order. The known bound has an elementary proof here, so numerical agreement is not being used as its justification.

Outcome.
Outcome: Exploratory approach with unresolved gap.

The attempt reconstructs a rigorous connected-domination lower bound for clique minors and isolates a sufficient chromatic-retention lemma. It also proves what any smallest counterexample would have to do to every connected dominating set. No exact colouring theorem beyond the established cases is obtained, and no counterexample to the original conjecture is produced. A continuation needs new control of chromatic loss or a different disjoint branch-set construction; the size estimate alone cannot provide it.

Sources

  • S1 Lafferty and Song, Every graph with no K_8^{-4} minor is 7-colorable $2022$, abstract. https://arxiv.org/abs/2208.07338. Catalogue formulation source.
  • S2 Beyond halfway to Hadwiger's conjecture. https://arxiv.org/abs/2609.06867v2. Catalogue research/status reference; not a proof endorsement.
  • S3 Disproof of the Odd Hadwiger Conjecture. https://arxiv.org/abs/2512.20392. Catalogue research/status reference; not a proof endorsement.
  • E1 Chun-Hung Liu and Jason Luo, Beyond halfway to Hadwiger's conjecture, arXiv:2609.06867v2, 9 September 2026, abstract and main theorem. https://arxiv.org/abs/2609.06867v2. Inspected 27 September 2026; the $O(t\log\log\log t)$ claim is a recent preprint theorem and not independently audited here. The prior Delcourt--Postle bound is described in its introduction.
  • E2 Pierre Duchet and Henri Meyniel, On Hadwiger's number and the stability number, in Graph Theory, North-Holland Mathematics Studies 62 $1982$, 71--73, DOI 10.1016/S0304-0208$08$73549-7. https://doi.org/10.1016/S0304-0208(08)73549-7. Classical attribution; the connected-domination proof and all inequalities used in this attempt are supplied explicitly.

Go to contribution →