Pith. sign in

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 →

arxiv 2507.03244 v1 pith:ULFD3GCX submitted 2025-07-04 math.CO

classification math.CO MSC 05C1505C8305C35
keywords Hadwiger'sconjecturegraphminors6-colorabilityK7∨-minorrootedcontraction-criticalgraphsMoserspindleextremaltheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that any graph avoiding the graph $K_7^{\vee}$ as a minor — the complete graph on seven vertices with two edges sharing an endpoint removed — can be properly colored with six colors. This is a strengthening of the earlier result that required excluding both $K_7^{\vee}$ and the matching-deletion graph $K_7^{=}$; here the single forbidden minor suffices. The argument assumes a hypothetical 7-chromatic counterexample, then uses a new extremal theorem to show it must be edge-dense and 4-connected, with many degree-seven vertices. Each such vertex forces a 5-clique in its neighborhood, and the intersection pattern of those 5-cliques is shown to be impossible. Consequently, any graph needing seven colors must contain $K_7^{\vee}$ as a minor, a concrete step toward the t=7 case of Hadwiger's conjecture.

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.

Watch

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 extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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'.
  5. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 10 assumptions · 0 invented entities

The proof is a traditional graph-theoretic derivation that rests on a substantial toolkit of deep prior results (RST93, Jørgensen, KT05, KLNZ05, Mader, Dirac, Kriesell-Mohr) and on finite structural case analyses that are partly delegated. There are no free parameters and no newly postulated entities. The Four Color Theorem is inherited through the RST93 black boxes. The main new content is Theorem 6 and its supporting Lemma 12, plus the clique-counting argument in Section 4.

assumptions (10)
  • domain assumption Four Color Theorem (through Wagner and RST93)
    Inherited via the cited Robertson-Seymour-Thomas structural results (Theorem 8 and Theorem 13 come from [RST93], whose proof of Hadwiger's conjecture for t=6 reduces to 4CT). The paper does not reprove 4CT.
  • domain assumption RST93 (2.6) structural dichotomy for rooted K4-models (Theorem 8)
    Used in Lemma 9 to bound |E(G)| ≤ 3|V(G)| - 7 when no Z-rooted K4-model exists; the planar outcome gives the edge bound.
  • domain assumption RST93 (2.4) crossing paths theorem (Theorem 13)
    Used in Claim 3.15 and at the end of Theorem 6 to force contradictions from terminal configurations.
  • domain assumption Jørgensen Lemma 16(2): internally 4-connected pair with |Z|=4 has a Z-rooted K4^- model (Lemma 10)
    Used in Lemma 12 and Claim 3.3 to find rooted K4^- models for edge-counting.
  • domain assumption Jørgensen Lemma 17 extremal bound for K4,2-models (Theorem 11)
    Starting point of Lemma 12, which upgrades the conclusion to K*_{4,2}-models.
  • domain assumption Kriesell-Mohr Lemma 2: Kempe chains yield rooted Ck-models (Theorem 14)
    Used in Claim 4.4 to convert a 6-coloring's Kempe chains into a C5-model. The cited source is an arXiv preprint (arXiv:1911.09998).
  • domain assumption Dirac's independent-neighborhood bound (Theorem 15)
    Used in Claim 4.4 to show N(v) has no independent set of size 3 for a degree-7 vertex.
  • domain assumption Mader's 7-connectivity theorem (Theorem 16)
    Used in Claim 4.1 to conclude the minimal counterexample is 7-connected.
  • domain assumption KT05 Lemma 3(i): three 5-cliques with common intersection of size 2 yield K7 (Lemma 17)
    Used in Claim 4.10 to exclude three 5-cliques all intersecting pairwise in 2 vertices.
  • domain assumption KLNZ05 complete-minor theorem (Theorem 18)
    Used in Claim 4.7 to bound |L1 ∪ L2 ∪ L3| ≤ 11 for any three 5-cliques.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2507.03244 by the authors.

Figure 1
Figure 1. The graph considered in the proof of Claim 4.4 (The Moser spindle). Claim 4.3 and Claim 4.4 immediately imply the following. Claim 4.5. | ∪L∈C L| ≥ 18. Claim 4.6. |L1 ∩ L2| ≤ 2 for all pairs of distinct L1, L2 ∈ C. Proof. If |L1 ∩ L2| = 4 then L1 ∪ L2 induces a K− 6 subgraph in G, contradicting Claim 4.2. Suppose now |L1 ∩ L2| = 3. As G \ (L1 ∩ L2) is 4-connected by Claim 4.1, there exist two vertex disjoint paths P… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [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

  2. [2]

    Appel and W

    K. Appel and W. Haken. Every planar map is four colorable. Part I: Discharging . Illinois Journal of Mathematics , 21(3):429 -- 490, 1977

  3. [3]

    Appel, W

    K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. Part II: Reducibility . Illinois Journal of Mathematics , 21(3):491 -- 567, 1977

  4. [4]

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

  5. [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

  6. [6]

    Hadwiger

    H. Hadwiger. Über eine K lassifikation der S treckenkomplexe. Vierteljahresschrift der Naturforschenden Gesellschaft Zürich , 88:133–143, 1943

  7. [7]

    I. T. Jakobsen. A homomorphism theorem with an application to the conjecture of H adwiger. Studia Scientiarum Mathematicarum Hungarica , 6:151–160, 1971

  8. [8]

    J rgensen

    Leif K. J rgensen. Contractions to K _8 . Journal of Graph Theory , 18(5):431–448, August 1994

Show all 21 references
  1. [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

  2. [10]

    Kempe chains and rooted minors

    Matthias Kriesell and Samuel Mohr. Kempe chains and rooted minors. arXiv preprint , arXiv:1911.09998, 2019

  3. [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

  4. [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

  5. [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

  6. [14]

    W. Mader. Homomorphieeigenschaften und mittlere K antendichte von G raphen. Mathematische Annalen , 174:265--268, 1967

  7. [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

  8. [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

  9. [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

  10. [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

  11. [19]

    Hadwiger s conjecture , pages 417--437

    Paul Seymour. Hadwiger s conjecture , pages 417--437. Springer International Publishing, January 2016

  12. [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

  13. [21]

    Extremal functions for rooted minors

    Paul Wollan. Extremal functions for rooted minors. Journal of Graph Theory , 58(2):159--178, 2008

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.