Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture

Gexin Yu; Ken-ichi Kawarabayashi

arxiv: 2606.01586 · v2 · pith:C7ZFIHI5new · submitted 2026-06-01 · 🧮 math.CO

Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture

Ken-ichi Kawarabayashi , Gexin Yu This is my paper

Pith reviewed 2026-06-28 14:31 UTC · model grok-4.3

classification 🧮 math.CO

keywords knitted graphsHadwiger conjecturevertex connectivitygraph minorslinkagecounterexamples

0 comments

The pith

Every 8ℓ-connected graph is ℓ-knitted, so minimal Hadwiger counterexamples have connectivity at least ⌈k/8⌉.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that any graph with vertex connectivity at least 8ℓ satisfies the ℓ-knitted property: for any set S of ℓ vertices and any partition of S into nonempty parts, the graph contains pairwise disjoint connected subgraphs each containing one part. This property is then fed into linkage arguments to show that no minimal counterexample to Hadwiger's conjecture (every k-chromatic graph has a K_k minor) can have vertex connectivity below ⌈k/8⌉. The new bound improves the earlier ⌈2k/27⌉ result and repairs a gap in a 2013 argument. A reader would care because the connectivity restriction narrows the search space for possible counterexamples to a central conjecture linking coloring and minors.

Core claim

We prove that every 8ℓ-connected graph is ℓ-knitted. We subsequently apply this result to Hadwiger's Conjecture, which states that every k-chromatic graph contains a K_k-minor. Specifically, we demonstrate that the vertex connectivity of any minimal counterexample to Hadwiger's Conjecture is at least ⌈k/8⌉, improving upon the previous lower bound of ⌈2k/27⌉.

What carries the argument

The ℓ-knitted property: for every subset S of ℓ vertices and every partition of S into nonempty subsets S1 to St, there exist pairwise disjoint connected subgraphs C1 to Ct with Si contained in Ci.

If this is right

Every graph that is 8ℓ-connected is ℓ-knitted.
The vertex connectivity of any minimal counterexample to Hadwiger's conjecture is at least ⌈k/8⌉.
The argument fixes a gap that existed in the 2013 linkage argument for the same claim.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same knitted property could be applied to obtain connectivity bounds for minimal counterexamples to other minor-closed conjectures.
A smaller constant than 8 in the connectivity-to-knitted implication would immediately raise the Hadwiger bound further.
The result may combine with newer linkage theorems to produce connectivity guarantees stronger than ⌈k/8⌉ for the same class of graphs.

Load-bearing premise

The knitted property established for 8ℓ-connectivity transfers directly to a connectivity lower bound for minimal Hadwiger counterexamples through the linkage arguments used in the cited earlier papers.

What would settle it

A minimal counterexample to Hadwiger's conjecture whose vertex connectivity is strictly less than ⌈k/8⌉ would falsify the connectivity claim.

read the original abstract

For a given subset $S\subseteq V(G)$ of a graph $G$, the pair $(G,S)$ is \emph{knitted} if for every partition of $S$ into non-empty subsets $S_1, S_2, \ldots, S_t$, there exist pairwise disjoint connected subgraphs $C_1, C_2, \ldots, C_t$ in $G$ such that $S_i\subseteq V(C_i)$ for all $1 \le i \le t$. A graph $G$ is \emph{$\ell$-knitted} if $(G,S)$ is knitted for every subset $S\subseteq V(G)$ of size $\ell$. In this paper, we prove that every $8\ell$-connected graph is $\ell$-knitted. We subsequently apply this result to Hadwiger's Conjecture, which states that every $k$-chromatic graph contains a $K_k$-minor. Specifically, we demonstrate that the vertex connectivity of any minimal counterexample to Hadwiger's Conjecture is at least $\lceil k/8 \rceil$, improving upon the previous lower bound of $\lceil 2k/27 \rceil$ established by Kawarabayashi (2007). Our proof corrects a gap in the argument of Kawarabayashi-Yu~(2013) and establishes the claim stated without proof in Liu--Rolek--Yu~(2019).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves every 8ℓ-connected graph is ℓ-knitted and raises the connectivity lower bound on minimal Hadwiger counterexamples from ⌈2k/27⌉ to ⌈k/8⌉ while fixing the 2013 gap.

read the letter

The core advance is the 8ℓ-knitted theorem, which improves the earlier connectivity bound on minimal counterexamples to Hadwiger's conjecture and corrects the gap left in Kawarabayashi-Yu 2013. The new bound ⌈k/8⌉ is a clear quantitative step up from the 2007 result, and the argument transfers the knitted property through the linkage tools already in the literature.

The paper does the technical work cleanly. It states the knitted definition explicitly, shows the 8ℓ-connectivity suffices for the partition-and-linkage property, and applies it directly to the Hadwiger setting without introducing new parameters or circular steps. The correction to the 2013 argument is presented as part of the same proof, which is useful for anyone who has cited that paper.

The main limitation is that 8 is still far from the conjectured optimum, but that is expected in this area and the paper does not claim otherwise. The multiplier comes from the standard linkage estimates rather than any ad-hoc fitting. I see no internal contradiction or unsupported transfer in the claims.

This is for specialists in graph minors and Hadwiger-type problems. Anyone tracking quantitative bounds on counterexamples will want the updated number and the gap fix. The work is grounded enough and the result is new enough that it should go to referees rather than be desk-rejected.

Referee Report

0 major / 2 minor

Summary. The paper proves that every 8ℓ-connected graph is ℓ-knitted, meaning that for any set S of ℓ vertices and any partition of S into nonempty subsets, there exist pairwise disjoint connected subgraphs each containing one part of the partition. It then applies this to Hadwiger's conjecture, showing that the vertex-connectivity of any minimal counterexample is at least ⌈k/8⌉ (improving the prior ⌈2k/27⌉ bound of Kawarabayashi 2007). The argument corrects a gap in Kawarabayashi-Yu (2013) and establishes the claim stated without proof in Liu-Rolek-Yu (2019).

Significance. If the central derivation holds, the result strengthens the known connectivity thresholds for the knitted property and yields a concrete improvement to the structural constraints on minimal Hadwiger counterexamples. The explicit correction of the cited gap and the direct use of linkage arguments from the referenced prior works constitute a clear advance in the area.

minor comments (2)

The abstract and introduction should explicitly state the section in which the gap in Kawarabayashi-Yu (2013) is identified and corrected.
Notation for the partition of S and the corresponding subgraphs C_i is introduced in the abstract; ensure the same symbols are used consistently in the first definition section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main results, and recommendation to accept. The referee correctly notes the improvement to the connectivity bound for minimal Hadwiger counterexamples and the correction of the gap in Kawarabayashi-Yu (2013).

Circularity Check

0 steps flagged

No significant circularity; central claim is an independent proof correcting prior gap

full rationale

The paper states and proves that every 8ℓ-connected graph is ℓ-knitted as a new result, then applies it to improve the Hadwiger connectivity bound using linkage arguments from cited prior works. Self-citations exist (Kawarabayashi 2007, Kawarabayashi-Yu 2013, Liu-Rolek-Yu 2019) but are not load-bearing for the new theorem; the proof corrects an explicit gap and supplies the missing argument. No self-definitional reduction, fitted-parameter prediction, or ansatz smuggling is present. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions of vertex-connectivity, minors, and chromatic number from prior graph theory literature; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Standard definitions of vertex-connectivity, graph minors, and chromatic number hold.
Invoked implicitly throughout the abstract when stating the knitted property and Hadwiger's conjecture.

pith-pipeline@v0.9.1-grok · 5796 in / 1235 out tokens · 36954 ms · 2026-06-28T14:31:38.158657+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[1]

Bollob´ as and A

B. Bollob´ as and A. Thomason. Highly linked graphs.Combinatorica, 16(3):313–320, 1996

1996
[2]

G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs.J. London Math. Soc., 27:85–92, 1952

1952
[3]

R. J. Faudree, R. J. Gould, A. V. Kostochka, L. Lesniak, I. Schiermeyer, and A. Saito. Degree conditions for k-ordered Hamiltonian graphs.J. Graph Theory, 42(3):199–210, 2003

2003
[4]

Kawarabayashi

K. Kawarabayashi. On the connectivity of minimum and minimal counterexamples to Hadwiger’s conjecture.J. Combin. Theory Ser. B, 97(1):144–150, 2007

2007
[5]

Kawarabayashi and B

K. Kawarabayashi and B. Toft. Any 7-chromatic graphs hasK7 orK 4,4 as a minor.Combinatorica, 25(3):327–353, 2005

2005
[6]

Kawarabayashi and G

K. Kawarabayashi and G. Yu. Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger’s Conjecture.J. Combin. Theory, Ser. B, 103:320–326, 2013

2013
[7]

R. Liu, M. Rolek, and Gexin Yu. Minimum degree condition for a graph to be knitted.Discrete Math., 342(11):3225–3228, 2019

2019
[8]

W. Mader. ¨Uber trennende Eckenmengen in homomorphiekritischen Graphen.Math. Ann., 175:243–252, 1968

1968
[9]

Robertson, P

N. Robertson, P. Seymour, and R. Thomas. Hadwiger’s conjecture forK 6-free graphs.Combinatorica, 13(3):279– 361, 1993

1993
[10]

Thomas and P

R. Thomas and P. Wollan. An improved linear edge bound for graph linkages.European J. Combin., 26(3-4):309– 324, 2005

2005
[11]

B. Toft. On separating sets of edges in contraction-critical graphs.Math. Ann., 129–147, 1972

1972
[12]

K. Wagner. ¨Uber eine eigenschaft der ebenen komplexe.Math. Ann., 114:570–590, 1937. 9 National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan. Email address:k keniti@nii.ac.jp Department of Mathematics, College of William and Mary, Williamsburg, V A 23185. Email address:gyu@wm.edu 10

1937

[1] [1]

Bollob´ as and A

B. Bollob´ as and A. Thomason. Highly linked graphs.Combinatorica, 16(3):313–320, 1996

1996

[2] [2]

G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs.J. London Math. Soc., 27:85–92, 1952

1952

[3] [3]

R. J. Faudree, R. J. Gould, A. V. Kostochka, L. Lesniak, I. Schiermeyer, and A. Saito. Degree conditions for k-ordered Hamiltonian graphs.J. Graph Theory, 42(3):199–210, 2003

2003

[4] [4]

Kawarabayashi

K. Kawarabayashi. On the connectivity of minimum and minimal counterexamples to Hadwiger’s conjecture.J. Combin. Theory Ser. B, 97(1):144–150, 2007

2007

[5] [5]

Kawarabayashi and B

K. Kawarabayashi and B. Toft. Any 7-chromatic graphs hasK7 orK 4,4 as a minor.Combinatorica, 25(3):327–353, 2005

2005

[6] [6]

Kawarabayashi and G

K. Kawarabayashi and G. Yu. Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger’s Conjecture.J. Combin. Theory, Ser. B, 103:320–326, 2013

2013

[7] [7]

R. Liu, M. Rolek, and Gexin Yu. Minimum degree condition for a graph to be knitted.Discrete Math., 342(11):3225–3228, 2019

2019

[8] [8]

W. Mader. ¨Uber trennende Eckenmengen in homomorphiekritischen Graphen.Math. Ann., 175:243–252, 1968

1968

[9] [9]

Robertson, P

N. Robertson, P. Seymour, and R. Thomas. Hadwiger’s conjecture forK 6-free graphs.Combinatorica, 13(3):279– 361, 1993

1993

[10] [10]

Thomas and P

R. Thomas and P. Wollan. An improved linear edge bound for graph linkages.European J. Combin., 26(3-4):309– 324, 2005

2005

[11] [11]

B. Toft. On separating sets of edges in contraction-critical graphs.Math. Ann., 129–147, 1972

1972

[12] [12]

K. Wagner. ¨Uber eine eigenschaft der ebenen komplexe.Math. Ann., 114:570–590, 1937. 9 National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan. Email address:k keniti@nii.ac.jp Department of Mathematics, College of William and Mary, Williamsburg, V A 23185. Email address:gyu@wm.edu 10

1937