{"id":"38904d3f-72ef-4224-b8ee-935c54ce3f95","arxiv_id":"2606.18462","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"low","formal_verification":"partial","parameter_count":0,"one_line_summary":"No 6-regular 4-vertex-critical graphs on n≤15 except one on 13 vertices; every 6-edge-cut in a 6-regular (4,1)-graph is a vertex star or has shores ≥15, with no bipartite shores on nontrivial cuts.","lead":"The paper computationally proves no 6-regular 4-vertex-critical graphs exist on 15 or fewer vertices except one unique example on 13 vertices, and derives exact structural properties of 6-edge-cuts in 6-regular (4,1)-graphs. A generalist might read it for concrete progress on the last open case of Dirac's 1970 question about critical graphs without critical edges.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"Exhaustiveness of the n≤15 computational enumeration for 6-regular 4-vertex-critical graphs","rationale":"The reader correctly flags the enumeration + cut-matrix classification as the weakest link. The Lean-checked lemmas strengthen the analytic parts (boundary-shortfall, coloring arguments in Theorem C) but do not cover the search. Because the central size bound and the “both shores ≥15” statement flow directly from that search, the concern is load-bearing yet does not require changing the CONDITIONAL verdict; it simply confirms why the is low.","tokens_in":1980,"tokens_out":360,"duration_ms":16376,"concrete_test":"Independently regenerate all 6-regular graphs on 13–15 vertices (via nauty/geng with degree sequence filter) and test each for 4-vertex-criticality using a 3-coloring oracle on G-v for every v; compare the resulting list against the paper’s claimed unique 13-vertex example. Any additional graph falsifies the n≤15 claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem A asserts there are no 6-regular 4-vertex-critical graphs on ≤15 vertices except one on 13 vertices (whose critical edges form a Hamilton cycle). This rests on a computer search whose completeness is asserted but not formally verified in the same way as the Lean-checked lemmas. The derived claim that every 6-regular (4,1)-graph has ≥16 vertices, and the subsequent use of the 21 cut matrices plus boundary-shortfall lemma for Theorem B, inherit this dependency. If the enumeration missed an isomorphism class or misclassified criticality/regularity, both the size lower bound and the cut classification for small orders would not hold.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":2122,"tokens_out":773,"duration_ms":18469,"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":[{"comment":"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.","section":"Theorem A"},{"comment":"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.","section":"cut-matrix classification (preceding Theorem B)"}],"minor_comments":[{"comment":"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.","section":"Theorem A"},{"comment":"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.","section":"Theorem C"}],"recommendation":"major_revision","confidential_remarks":"The computational component of Theorem A is the primary source of the low confidence; if the authors can supply the enumeration code and a reproducibility statement, the manuscript would be substantially stronger for this journal."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the detailed and constructive report. We respond to each major comment below.","responses":[{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."}],"tokens_in":1821,"tokens_out":574,"duration_ms":32406,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that any 6-regular (4,1)-graph must have at least 16 vertices, with every 6-edge-cut either a vertex star or having shores of size at least 15, and the paper supplies the exact list of 21 possible 3x3 cut matrices plus a boundary-shortfall lemma to prove it.\n\nWhat stands out is the concrete classification work and the Lean-checked lemmas. The non-existence claim for n≤15, the super-6-edge-connectivity corollary up to order 29, and the color-forcing statement in Theorem C are new relative to the Skottova-Steiner results cited. The matrix enumeration and the observation that the unique near-miss is K_{3,3,3} minus a rainbow matching give explicit tools that later papers could use when trying to settle existence for larger orders.\n\nThe computational enumeration for n≤15 is the clearest soft spot. Its completeness is asserted but not Lean-verified in the same way as the supporting lemmas, so the size lower bound and the small-order part of the cut classification inherit that dependency. If an isomorphism class was missed or criticality was misjudged, both Theorem A and the downstream claims for n≤29 would need adjustment. The structural lemmas themselves look more robust.\n\nThis is narrow work aimed at people already following Dirac's k=4 problem and the (4,1)-graph literature. A reader who needs concrete constraints on edge-cuts or small-order obstructions will get usable statements and references. It is worth sending to peer review because the new classification and the formal checks provide something definite to evaluate, even if the computation requires extra scrutiny on the enumeration side.","headline":"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.","tokens_in":2642,"tokens_out":430,"would_cite":false,"duration_ms":18040,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"There is no 6-regular 4-vertex-critical graph on 15 or fewer vertices except one unique graph on 13 vertices.","keywords":["6-regular graphs","4-vertex-critical graphs","(4,1)-graphs","edge-cuts","superconnectivity","Dirac's k=4 problem","chromatic critical graphs"],"falsifier":"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.","tokens_in":2864,"feed_emoji":"","tokens_out":792,"duration_ms":32724,"temperature":0.7,"pith_summary":"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.","feed_headline":"No 6-regular 4-critical graphs below 16 vertices except one on 13","feed_subtitle":"Enumeration rules out smaller candidates, forcing any 6-regular (4,1)-graph to have 16 or more vertices.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["No 6-regular 4-critical graphs on 15 or fewer vertices except one on 13","Unique 13-vertex 6-regular 4-critical graph only case below 16 vertices","6-regular 4-critical graphs require 16 vertices minimum with 13-vertex exception","Sole 6-regular 4-critical graph below 16 vertices is the 13-vertex example"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No 6-regular 4-critical graphs on 15 or fewer vertices except one on 13","Unique 13-vertex 6-regular 4-critical graph only case below 16 vertices","6-regular 4-critical graphs require 16 vertices minimum with 13-vertex exception","Sole 6-regular 4-critical graph below 16 vertices is the 13-vertex example"]},"model":"grok-4.3","cost_usd":0.011762,"raw_usage":{"total_tokens":5255,"prompt_tokens":885,"num_sources_used":0,"completion_tokens":95,"cost_in_usd_ticks":117624500,"prompt_tokens_details":{"text_tokens":885,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":4275,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":885,"tokens_out":95,"duration_ms":32897,"temperature":1.0,"reasoning_tokens":4275,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T23:28:12.748623+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}