REVIEW 3 major objections 5 minor 21 references
Every graph with no $K_7^{\vee}$-minor is $6$-colorable
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Every graph with no $K_7^{\vee}$-minor is 6-colorable.
desk verdict A genuinely new strengthening of Jakobsen's theorem and a reusable extremal density result, but the proof of Claim 4.4 has a load-bearing gap that needs a substantive fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The main working object is the rooted model: a family of disjoint connected subgraphs (bags), each containing a prescribed root vertex, with edges prescribed between bags; contracting the bags produces a desired minor. The proof's engine is a refined rooted-model lemma: an internally 4-connected graph with no rooted $K^*_{4,2}$-model has at most $4|V| - 10$ edges, derived from trisection and crossing-path theorems and from prior extremal rooted-minor lemmas. In the coloring half, the decisive combinatorial device is the intersection pattern of 5-cliques: any three distinct 5-cliques must intersect in sizes 2, 2, 1, which forces the clique-intersection graph to be bipartite even though the proof needs it to be non-bipartite and large.
What would settle it
A direct counterexample: a single 7-chromatic graph with no $K_7^{\vee}$-minor would refute Theorem 4; a concrete search target would be any 7-contraction-critical graph on at least 18 vertices whose degree-seven neighborhoods all pass the Claim 4.4 case analysis but whose 5-clique family nevertheless satisfies Claim 4.10. Alternatively, an exhaustive computer check of all 4-connected graphs on 9--12 vertices looking for one with $|E| \ge 4|V| - 8$, not isomorphic to $K_{2,2,2,2}$, and no $K_7^{\vee}$-minor would settle Theorem 6.
Extended reading notes
Core claim
The central theorem, Theorem 4, asserts that every graph with no $K_7^{\vee}$-minor is 6-colorable; equivalently, every 7-chromatic graph contains $K_7^{\vee}$ as a minor. The load-bearing subclaim, Theorem 6, is an extremal statement: every 4-connected graph $G$ with $|E(G)| \ge 4|V(G)| - 8$ has a $K_7^{\vee}$-minor unless $G \simeq K_{2,2,2,2}$. The proof obtains this by taking a minor-minimal counterexample, eliminating 4-separations and vertices of degree five and seven, and then ruling out the surviving degree-six case through a planar/separation argument. On the coloring side, the paper shows a 7-contraction-critical graph would have at least 18 degree-seven vertices, each living in a 5-clique, and then proves the family of such 5-cliques cannot satisfy the required intersection constraints. Therefore no counterexample exists.
Load-bearing premise
The load-bearing premise is that the finite check of all possible neighborhoods of a degree-seven vertex is exhaustive, leaving only one special seven-vertex configuration (the Moser spindle) in the no-4-clique case; if any configuration was missed, the proof that the counterexample has many 5-cliques would collapse.
Editorial extensions
If this is right
- Every 7-chromatic graph contains $K_7^{\vee}$ as a minor, so any potential counterexample to Hadwiger's conjecture for $t=7$ would have to contain this near-complete minor even while avoiding $K_7$.
- Theorem 6 gives a sharp edge threshold: a 4-connected graph with $|E(G)| \ge 4|V(G)| - 8$ is either $K_{2,2,2,2}$ or has a $K_7^{\vee}$-minor; consequently, in the 4-connected $K_7^{\vee}$-minor-free setting the edge count is at most $4|V| - 9$ apart from that one exception.
- A 7-contraction-critical graph that avoids $K_7^{\vee}$ would need at least 18 vertices of degree seven, and each of those vertices must lie in a 5-clique; the paper shows this configuration is structurally impossible.
- The earlier 6-colorability theorem of Jakobsen is upgraded: excluding $K_7^{\vee}$ alone, without excluding the two-edge-matching deletion $K_7^{=}$, is enough to force 6-colorability.
Reading between the lines
- Editorial: the same rooted-model toolkit may prove an analogous 5-connected extremal theorem for $K_7^{=}$ at the threshold $4|V|-9$, which the paper states as Conjecture 20; if that holds, the full delete-two-edges family would be covered.
- Editorial: the 'moderately routine case analysis' in Claim 4.4 is a finite verification gap; a machine-certified enumeration of all seven-vertex neighborhoods with no independent set of size three and no 4-clique would independently settle that step.
- Editorial: because Theorem 6 explicitly isolates $K_{2,2,2,2}$ as the only exception at $4|V|-8$, edge modifications of this graph (adding or deleting a few edges) are natural test cases for whether the threshold is tight in the 4-connected class.
- Editorial: the 5-clique intersection theorem suggests a transferable principle—large families of nearly disjoint large cliques in critically colored graphs force complete minors—whose extension to $K_8$ and $K_9$ deletion-minor colorability could shorten the analogous proofs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that every graph with no K_7^∨-minor is 6-colorable, strengthening Jakobsen's theorem that excluded both K_7^∨ and K_7^=. The proof follows the contraction-critical framework: assuming a minor-minimal 7-chromatic counterexample, it establishes an extremal theorem (Theorem 6) asserting that every 4-connected graph with |E| ≥ 4|V| − 8 has a K_7^∨-minor unless it is K_{2,2,2,2}. This is used to show that the counterexample has many degree-7 vertices, whose closed neighborhoods are claimed to contain 5-cliques (Claim 4.4). The final stage analyzes the intersections of these 5-cliques to force a K_7 minor, contradicting the minor-minimality. The argument imports several external theorems (RST93, Jørgensen, KT05, KLNZ05, Mader, Dirac, Kriesell–Mohr) and contains several finite case analyses that are sketched rather than fully derived.
Significance. If correct, the main theorem is a genuine strengthening of a 1971 result of Jakobsen and brings the t = 7 case of Hadwiger's conjecture closer to resolution. Theorem 6, the new extremal result for K_7^∨-minors in 4-connected graphs, is of independent interest and parallels Jørgensen's theorem for K_{4,4}-minors. The paper is self-contained modulo published theorems, makes no use of fitted parameters, and its central claim is concrete and falsifiable. The main weaknesses are that several load-bearing case analyses are only sketched or delegated, and one inference in Claim 4.4 appears, as written, to be unsupported; these issues must be repaired before the result can be considered established.
major comments (3)
- [Section 4, Claim 4.4 (final paragraph)] The conclusion 'Contracting the bags of this model, we obtain a minor of G which induces K_7^∨ on N[v] − {u'_4}' does not follow from the preceding argument. A rooted C5-model guarantees only that, after contracting the five bags, the resulting vertices form a cycle; it does not guarantee that they form a K5. In K_7^∨, the five bag-vertices must be pairwise adjacent, giving 10 edges among them, whereas the C5-model supplies only the five cycle edges. The Kempe-chain bags may contain vertices outside N[v], so the adjacencies of u'_3 to the bags are not controlled by the Moser-spindle structure inside N(v). Together with the star from v, the edge count is at most 12 guaranteed edges plus the five cycle edges, far short of the 19 edges of K_7^∨; no argument is given for the missing edges. This is load-bearing because Claim 4.4 is what produces the 5-cliques used in Claims 4.5–4.10.
- [Section 4, Claim 4.4 (first paragraph)] The assertion that every 7-vertex graph H with α(H) ≤ 2 and ω(H) ≤ 3 contains a subgraph isomorphic to the Moser spindle is justified only by a reference to '[KT05, Section 2]' and the phrase 'moderately routine case analysis'. This finite classification is not derived in the paper, and it is the only route from a degree-7 vertex to a 5-clique. The authors should either supply the complete case analysis or provide a precise statement and location of a lemma in KT05 that proves exactly this classification; as written, the claim cannot be independently verified by the reader.
- [Section 3, Claim 3.11] Each of the five cases for the complement H of G[N(v)] is dismissed in a single sentence of the form 'contracting ... we obtain a minor inducing K_7^∨ on N[v]'. Because Claim 3.11 is essential for the proof of Theorem 6, these five finite verifications are load-bearing. The description of the contractions is too terse to confirm that the resulting minor indeed has all edges of K_7^∨; a missed adjacency pattern in any of the five cases would invalidate the extremal theorem. The authors should describe the resulting minor explicitly for each case, or provide a machine-checkable certificate.
minor comments (5)
- [Section 2, Lemma 9, equation (1)] The displayed equation contains an arithmetic error: after obtaining |E(G)| ≤ 3|B| − 2 = 3(|V(G)| − 2) − 2, the text writes '≤ 3|B| − 8', which is inconsistent. The intended bound is |E(G)| ≤ 3|V(G)| − 8; this should be corrected.
- [Section 4, Claim 4.10] In the case |Z| = 1, the sentence 'L1 ∪ (L2 ∩ L3) induces a supergraph of K_7^∨' cannot be correct, since the set has only six vertices; it should read K_6^∨ (or K_7^∨ should be replaced by K_6^∨). The argument itself is valid because the unique vertex in (L2 ∩ L3) \ L1 is adjacent to at least three vertices of the 5-clique L1.
- [Section 3, Claim 3.15, third bullet] In the final case of Claim 3.15, the notation 'y ∈ B′ − A′' is used, but the sets A′ and B′ have not been introduced in that paragraph; this makes the argument difficult to follow and should be clarified.
- [Section 4, Claim 4.10, first sentence] The phrase 'It remains to show exclude the case' is missing the word 'to'; it should read 'It remains to show how to exclude the case'.
- [Section 1, Introduction] The description of reference [RST23] as discussing 'minor minimal non-7-colorable graphs with no K7-minor' appears to be inaccurate; the cited paper concerns 8-contraction-critical graphs with no K7 minor. The sentence should be corrected.
Circularity Check
No significant circularity: the proof is an independent extension built on cited external theorems, with no fitted inputs, self-citations, or by-construction reductions.
full rationale
The paper's central claim, Theorem 4, is derived from Theorem 6, an extremal result proved in Section 3 using external results of Robertson–Seymour–Thomas, Jørgensen, and others. Section 4 then uses theorems of Dirac, Mader, Kawarabayashi–Toft, Kawarabayashi–Luo–Niu–Zhang, and Kriesell–Mohr. None of these cited works are by the present authors, and no parameter is fitted to data or renamed as a prediction. The Moser-spindle assertion in Claim 4.4 is delegated to [KT05, Section 2] and routine case analysis; even if that step is underjustified, that is a correctness or rigor concern, not circularity, because it does not reduce the theorem to its own assumptions. The derivation does not define its target in terms of itself, does not invoke a self-citation as load-bearing, and does not smuggle in the desired conclusion via an ansatz. The external benchmark results (RST93, Jørgensen, KT05) are independent published theorems, so the chain is self-contained in the relevant sense. Thus the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (10)
- domain assumption Four Color Theorem (through Wagner and RST93)
- domain assumption RST93 (2.6) structural dichotomy for rooted K4-models (Theorem 8)
- domain assumption RST93 (2.4) crossing paths theorem (Theorem 13)
- domain assumption Jørgensen Lemma 16(2): internally 4-connected pair with |Z|=4 has a Z-rooted K4^- model (Lemma 10)
- domain assumption Jørgensen Lemma 17 extremal bound for K4,2-models (Theorem 11)
- domain assumption Kriesell-Mohr Lemma 2: Kempe chains yield rooted Ck-models (Theorem 14)
- domain assumption Dirac's independent-neighborhood bound (Theorem 15)
- domain assumption Mader's 7-connectivity theorem (Theorem 16)
- domain assumption KT05 Lemma 3(i): three 5-cliques with common intersection of size 2 yield K7 (Lemma 17)
- domain assumption KLNZ05 complete-minor theorem (Theorem 18)
Cite this review
Pith. "Pith review of Every graph with no $K_7^{\vee}$-minor is $6$-colorable." pith.science (2026). https://pith.science/paper/ULFD3GCX
@misc{pith2026250703244,
author = {Pith},
title = {Pith review of: Every graph with no $K_7^\vee$-minor is $6$-colorable},
year = {2026},
howpublished = {\url{https://pith.science/paper/ULFD3GCX}},
note = {Machine review of arXiv:2507.03244}
}
abstract
Let $K_7^{\vee}$ denote the graph obtained from the complete graph on seven vertices by deleting two edges with a common end. Motivated by Hadwiger's conjecture, we prove that every graph with no $K_7^{\vee}$-minor is $6$-colorable.
Figures
Reference graph
Works this paper leans on
-
[1]
On triangles in K_r -minor free graphs
Boris Albar and Daniel Gon c alves. On triangles in K_r -minor free graphs . Journal of Graph Theory , 88(1):154--173, May 2018
work page 2018
-
[2]
K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging . Illinois Journal of Mathematics , 21(3):429 -- 490, 1977
work page 1977
- [3]
-
[4]
G. A. Dirac. A property of 4 -chromatic graphs and some remarks on critical graphs. J. London Math. Soc. , 27:85--92, 1952
work page 1952
-
[5]
G.A. Dirac. Trennende K notenpunktmengen und R eduzibilität abstrakter G raphen mit A nwendung auf das V ierfarbenproblem. Journal für die Reine und Angewandte Mathematik , 204:116--131, 1960
work page 1960
- [6]
-
[7]
I. T. Jakobsen. A homomorphism theorem with an application to the conjecture of H adwiger. Studia Scientiarum Mathematicarum Hungarica , 6:151–160, 1971
work page 1971
- [8]
Show all 21 references
-
[9]
On the structure of k -connected graphs without K _k -minor
Ken-ichi Kawarabayashi, Rong Luo, Jianbing Niu, and Cun-Quan Zhang. On the structure of k -connected graphs without K _k -minor. European Journal of Combinatorics , 26(3):293--308, 2005. Topological Graph Theory and Graph Minors, second issue
2005
-
[10]
Kempe chains and rooted minors
Matthias Kriesell and Samuel Mohr. Kempe chains and rooted minors. arXiv preprint , arXiv:1911.09998, 2019
1911 arXiv
-
[11]
Any 7-chromatic graph has K _7 or K _ 4,4 as a minor
Ken-ichi Kawarabayashi and Bjarne Toft. Any 7-chromatic graph has K _7 or K _ 4,4 as a minor. Combinatorica , 25:327--353, 2005
2005
-
[12]
Every graph with no K _8^ -4 minor is 7 -colorable
Michael Lafferty and Zi-Xia Song. Every graph with no K _8^ -4 minor is 7 -colorable. arXiv preprint 2208.07338 , 2022
2022 arXiv
-
[13]
Every graph with no K _9^ -6 minor is 8 -colorable
Michael Lafferty and Zi-Xia Song. Every graph with no K _9^ -6 minor is 8 -colorable. arXiv preprint arXiv:2209.05259 , 2022
2022 arXiv
-
[14]
W. Mader. Homomorphieeigenschaften und mittlere K antendichte von G raphen. Mathematische Annalen , 174:265--268, 1967
1967
-
[15]
Graphs with no K_9^= -minor are 10 -colorable
Martin Rolek. Graphs with no K_9^= -minor are 10 -colorable. Journal of Graph Theory , 93(4):560--565, 2020
2020
-
[16]
Coloring graphs with forbidden minors
Martin Rolek and Zi-Xia Song. Coloring graphs with forbidden minors. Journal of Combinatorial Theory, Series B , 127:14--31, 2017
2017
-
[17]
Hadwiger's conjecture for K _6 -free graphs
Neil Robertson, Paul Seymour, and Robin Thomas. Hadwiger's conjecture for K _6 -free graphs. Combinatorica , 13:279--361, 1993
1993
-
[18]
Properties of 8 -contraction-critical graphs with no K_7 minor
Martin Rolek, Zi-Xia Song, and Robin Thomas. Properties of 8 -contraction-critical graphs with no K_7 minor. European Journal of Combinatorics , 110:103711, 2023
2023
-
[19]
Hadwiger s conjecture , pages 417--437
Paul Seymour. Hadwiger s conjecture , pages 417--437. Springer International Publishing, January 2016
2016
-
[20]
\"U ber eine E igenschaft der ebenen K omplexe
Klaus Wagner. \"U ber eine E igenschaft der ebenen K omplexe. Mathematische Annalen , 114(1):570--590, 1937
1937
-
[21]
Extremal functions for rooted minors
Paul Wollan. Extremal functions for rooted minors. Journal of Graph Theory , 58(2):159--178, 2008
2008
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.