Pith. sign in

REVIEW 2 major objections 2 minor 5 references

Exact 6-cut rigidity and small-order superconnectivity for the 6-regular case of Dirac's k=4 problem

T0 review · 2 major / 2 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read There is no 6-regular 4-vertex-critical graph on 15 or fewer vertices except one unique graph on 13 vertices.

desk verdict The paper gives a computer-assisted non-existence result for 6-regular 4-critical graphs on n≤15 (except one on 13) plus an exhaustive classification of 6-edge-cuts into 21 matrices. read the letter →

arxiv 2606.18462 v1 pith:75N3RDC7 submitted 2026-06-16 math.CO

Alper Ferudun This is my paper · ORCID
classification math.CO
keywords 6-regulargraphs4-vertex-critical(41)-graphsedge-cutssuperconnectivityDirac'sk=4problemchromaticcritical
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 examines whether 6-regular (4,1)-graphs exist, graphs that are 4-chromatic, drop to 3-chromatic when any vertex is removed, and stay 4-chromatic when any edge is removed. Computation shows no 6-regular 4-vertex-critical graphs exist on 15 or fewer vertices except a single 13-vertex example whose critical edges form a Hamilton cycle. This sets a lower bound of 16 vertices for any 6-regular (4,1)-graph. The paper also classifies all 6-edge-cuts via 3x3 matrices and proves that nontrivial cuts have large shores and non-bipartite induced subgraphs on those shores.

What carries the argument

The exact classification of 21 possible 3x3 cut matrices for 6-edge-cuts in (4,1)-graphs (five types up to row/column permutation), together with the boundary-shortfall lemma.

What would settle it

A 6-regular 4-vertex-critical graph on 16 or fewer vertices that is not the known 13-vertex example, or a 6-edge-cut whose shores are smaller than 15 and not a vertex star.

Watch

Extended reading notes

Core claim

There is no 6-regular 4-vertex-critical graph on n ≤ 15 vertices, except for a unique graph on n=13 whose 13 critical edges form a Hamilton cycle; hence any 6-regular (4,1)-graph has at least 16 vertices. In a 6-regular (4,1)-graph every 6-edge-cut is either the edge star of a vertex or has both shores of size at least 15, and no shore of a nontrivial 6-edge-cut induces a bipartite graph.

Load-bearing premise

The computational enumeration of all 6-regular graphs on at most 15 vertices is exhaustive and the derived cut-matrix classification plus boundary-shortfall lemma covers every possible 6-edge-cut.

Editorial extensions

If this is right

  • Any 6-regular (4,1)-graph has at least 16 vertices.
  • Every 6-regular (4,1)-graph on at most 29 vertices is super-6-edge-connected.
  • No shore of a nontrivial 6-edge-cut in a 6-regular (4,1)-graph induces a bipartite graph.
  • A shore whose deficiency is concentrated on two vertices forces those vertices to receive equal colours in every proper 3-colouring.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The single 13-vertex 4-vertex-critical graph must contain at least one critical edge and therefore fails to be a (4,1)-graph.
  • The cut classification supplies a concrete obstruction that any future search for 6-regular (4,1)-graphs on 16 or more vertices must satisfy.
  • Formal verification of the supporting lemmas in Lean 4 suggests the same method could be applied to check superconnectivity claims up to the 29-vertex threshold.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper addresses Dirac's 1970 question on the existence of k-vertex-critical graphs without critical edges for k=4 (open after Jensen's resolution for k>=5). It focuses on 6-regular (4,1)-graphs, where chi(G)=4, chi(G-v)=3 for all v, and chi(G-e)=4 for all e. Theorem A computationally establishes that no 6-regular 4-vertex-critical graphs exist on n<=15 vertices except a unique (up to isomorphism) example on n=13 whose critical edges form a Hamilton cycle, implying any 6-regular (4,1)-graph has at least 16 vertices. Theorem B classifies all 6-edge-cuts in such graphs (every nontrivial 6-edge-cut has both shores of size at least 15) via an exhaustive list of 21 possible 3x3 cut matrices (five types up to permutation) and a boundary-shortfall lemma, implying super-6-edge-connectivity for n<=29. Theorem C proves that no shore of a nontrivial 6-edge-cut induces a bipartite graph (and a more general coloring statement). Several supporting lemmas are verified in Lean 4/Mathlib.

Significance. If the results hold, they supply the first concrete lower bound on the order of 6-regular (4,1)-graphs and structural constraints on their edge-cuts that narrow the search space for existence. The machine-checked lemmas and explicit computational non-existence for small n provide independent grounding for the non-computational claims. The cut-matrix classification and boundary-shortfall lemma, if exhaustive, offer a reusable tool for analyzing connectivity in vertex-critical graphs.

major comments (2)
  1. [Theorem A] Theorem A (and its use in the size lower bound feeding into Theorems B and C): the exhaustiveness of the computational enumeration of 6-regular 4-vertex-critical graphs on n<=15 is asserted without accompanying formal verification, code, or isomorphism-checking details comparable to the Lean-checked lemmas. If any isomorphism class was missed or misclassified with respect to regularity or criticality, the claim that every 6-regular (4,1)-graph has >=16 vertices (and the consequent superconnectivity statement for n<=29) would not hold.
  2. [cut-matrix classification (preceding Theorem B)] Section on cut-matrix classification (supporting Theorem B): the derivation that there are exactly 21 possible 3x3 cut matrices (five types up to row/column permutation) for 6-edge-cuts in (4,1)-graphs is presented as exhaustive, but the manuscript does not indicate whether this enumeration was itself machine-checked or cross-verified against all possible degree sequences consistent with 6-regularity and the (4,1) coloring conditions. This classification is load-bearing for the boundary-shortfall lemma and the shore-size conclusion.
minor comments (2)
  1. [Theorem A] The unique n=13 example is described as having its 13 critical edges forming a Hamilton cycle; a figure or explicit adjacency list would aid verification of this property.
  2. [Theorem C] The statement of Theorem C refers to 'deficiency concentrated on two vertices'; a precise definition of deficiency in terms of the cut matrix or coloring constraints would clarify the general claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Theorem A] Theorem A (and its use in the size lower bound feeding into Theorems B and C): the exhaustiveness of the computational enumeration of 6-regular 4-vertex-critical graphs on n<=15 is asserted without accompanying formal verification, code, or isomorphism-checking details comparable to the Lean-checked lemmas. If any isomorphism class was missed or misclassified with respect to regularity or criticality, the claim that every 6-regular (4,1)-graph has >=16 vertices (and the consequent superconnectivity statement for n<=29) would not hold.

    Authors: We acknowledge this valid concern regarding the presentation of the computational results in Theorem A. The enumeration was performed using standard graph generation tools with checks for regularity and criticality, including isomorphism filtering via nauty. To address the referee's point, in the revised manuscript we will include a detailed description of the computational procedure, the specific parameters used, and information on how isomorphisms were handled. We will also make the code and data available in a public repository to allow for independent verification. This will ensure the exhaustiveness claim is fully supported. revision: yes

  2. Referee: [cut-matrix classification (preceding Theorem B)] Section on cut-matrix classification (supporting Theorem B): the derivation that there are exactly 21 possible 3x3 cut matrices (five types up to row/column permutation) for 6-edge-cuts in (4,1)-graphs is presented as exhaustive, but the manuscript does not indicate whether this enumeration was itself machine-checked or cross-verified against all possible degree sequences consistent with 6-regularity and the (4,1) coloring conditions. This classification is load-bearing for the boundary-shortfall lemma and the shore-size conclusion.

    Authors: The 21 cut matrices were enumerated by considering all possible 3x3 nonnegative integer matrices with each row and column summing to 6, subject to the additional constraints imposed by the (4,1)-graph properties (specifically, that each shore must be 3-colorable with the color classes satisfying the criticality conditions). This is a finite and manageable set, which we enumerated exhaustively by hand, cross-checking against the possible distributions of edges between color classes. While this enumeration was not machine-checked (unlike the Lean-verified lemmas), its small size permits direct verification. In the revision, we will add a short subsection or paragraph detailing the enumeration process and the constraints used, to make the exhaustiveness explicit and allow readers to reproduce the classification. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; results rest on definitions, exhaustive enumeration, and machine-checked lemmas

full rationale

The derivation chain begins from standard definitions of vertex-criticality, (4,1)-graphs, and edge-cuts, proceeds via an exhaustive computational enumeration for n≤15 (presented as an independent check), derives a finite classification of 21 cut matrices from those definitions, and invokes a boundary-shortfall lemma plus Lean-verified supporting lemmas. No equations reduce to their inputs by construction, no parameters are fitted then renamed as predictions, and no load-bearing claims depend on self-citations or prior author work. The Lean machine-checks supply external verification independent of the present paper's fitted values or assertions.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper relies on standard definitions of chromatic number, vertex-criticality, and edge-cuts from prior literature; the new content is the derived classification of cut matrices and the computational result rather than additional axioms or free parameters.

assumptions (2)
  • standard math Standard definitions and properties of chromatic number, vertex-critical graphs, and edge-cuts in simple graphs
    Invoked in the definition of (4,1)-graphs and all cut analysis throughout the abstract.
  • domain assumption The boundary-shortfall lemma and completeness of the 3x3 cut-matrix classification for 6-edge-cuts
    Explicitly stated as the foundation for Theorem B.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exact 6-cut rigidity and small-order superconnectivity for the 6-regular case of Dirac's k=4 problem." pith.science (2026). https://pith.science/paper/75N3RDC7

@misc{pith2026260618462,
  author       = {Pith},
  title        = {Pith review of: Exact 6-cut rigidity and small-order superconnectivity for the 6-regular case of Dirac's k=4 problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/75N3RDC7}},
  note         = {Machine review of arXiv:2606.18462}
}
read the original abstract

Dirac asked in 1970 whether for every k >= 4 there is a k-vertex-critical graph without critical edges; Jensen settled all k >= 5, and only k=4 remains open. Following Skottova and Steiner, call a graph G a (4,1)-graph if chi(G)=4, chi(G-v)=3 for every vertex v, and chi(G-e)=4 for every edge e; they proved delta(G) >= 6 and lambda(G) >= 6 for every (4,1)-graph and asked whether a 6-regular (4,1)-graph exists. We prove three results about this 6-regular case. Theorem A (computational): there is no 6-regular 4-vertex-critical graph on n <= 15 vertices, except for a unique graph (up to isomorphism) on n=13, whose 13 critical edges form a Hamilton cycle; hence any 6-regular (4,1)-graph has at least 16 vertices. Theorem B: in a 6-regular (4,1)-graph every 6-edge-cut is either the edge star of a vertex or has both shores of size at least 15; consequently every 6-regular (4,1)-graph on at most 29 vertices is super-6-edge-connected. Theorem C (all sizes): no shore of a nontrivial 6-edge-cut in a 6-regular (4,1)-graph induces a bipartite graph; more generally, a shore whose deficiency is concentrated on two vertices forces them to receive equal colours in every proper 3-colouring. The proof of Theorem B rests on an exact classification of the 3x3 cut matrices of 6-edge-cuts in (4,1)-graphs (exactly 21 matrices, five types up to row/column permutations) together with a boundary-shortfall lemma; the unique near-miss is K_{3,3,3} minus a rainbow 3-matching. Several supporting lemmas are machine-checked in Lean 4/Mathlib.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 1 canonical work pages

  1. [1]

    Bloom,Erd˝ os problem #944, Online database of Erd˝ os problems,https://www

    T. Bloom,Erd˝ os problem #944, Online database of Erd˝ os problems,https://www. erdosproblems.com/944

  2. [2]

    Erd˝ os,On some aspects of my work with Gabriel Dirac, in: Graph Theory in Memory of G

    P. Erd˝ os,On some aspects of my work with Gabriel Dirac, in: Graph Theory in Memory of G. A. Dirac (Sandbjerg, 1985), Ann. Discrete Math.41, North-Holland, 1989, 111–116

    1985

  3. [3]

    T. R. Jensen,Dense critical and vertex-critical graphs, Discrete Math.258(2002), 63–84

    2002

  4. [4]

    T. R. Jensen and M. Siggers,On a question of Dirac on critical and vertex-critical graphs, Sib. `Elektron. Mat. Izv.9(2012), 156–160

    2012

  5. [5]

    Skottova and R

    E. Skottova and R. Steiner,Critical edge sets in vertex-critical graphs, arXiv:2508.08703 (2025). 9

    work page arXiv 2025

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.