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.