{"id":"c0699bb9-77c2-4b10-9f61-45b496665afd","arxiv_id":"2411.15992","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For non-bipartite planar cubic graphs with 2n vertices, the Heawood system has rank n+1, giving a defining set of n-1 vertices and at most 3 times 2^{n-1} Tait colorings; circular ladders have 2^n+8 colorings for even n and 2^n-2 for odd n.","lead":"A mathematics paper revives the 19th century Heawood method for counting edge colorings of cubic planar graphs and adds a geometric proof that its linear system has full rank for non-bipartite graphs. The result yields a tighter upper bound on the number of colorings, though a stronger version of the main count was already published by M. P. Ivanov, which the author discloses.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's proof of empty-zebra implies bipartite relies on a false alternation claim: an uncolored face bounded by an internal cycle may consist entirely of EC edges, so the proof of Theorem 2 is incomplete as written.","rationale":"The reader identified Lemmas 1 and 2 as the weakest link, and this is indeed where the central theorem's proof is most vulnerable. My stress-test found a concrete error in Lemma 2's proof: the alternation between EC and EP edges does not hold for uncolored faces enclosed by internal cycles, as the cube example shows. This is a genuine correctness gap in the proof as written. However, the lemma itself appears true, and a repair is evident: colored faces inside the zebra body alternate, while uncolored holes have even boundary length because the empty-zebra condition forces each boundary cycle C_i to have even length. The classical rank result (n+1 for non-bipartite graphs) also supports the theorem's conclusion. Since the flaw is repairable and does not falsify the central claim, the paper remains CONDITIONAL; the reader's verdict is unchanged, but the reason now includes a specific proof gap rather than only the acknowledged overstatement about prior work.","tokens_in":10315,"tokens_out":36286,"duration_ms":362636,"concrete_test":"Take the cube graph with the bottom face as the outer face, and set face coefficients: front = +1, back = +1, left = -1, right = -1, top = 0. Verify that every vertex has incident coefficient sum 0 mod 3, yielding a nonzero linear combination with empty support. Then trace the boundary of the uncolored top face: all four edges lie in EC, contradicting Lemma 2's assertion that every EC edge is followed by an EP edge. Finally, check whether the proof can be repaired by replacing that assertion with (i) EC/EP alternation only for faces inside the zebra body and (ii) evenness of each cycle C_i from the evenness of |W ∩ V(C_i)|; if no such repair is possible, Theorem 2's proof is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 depends on Lemma 2, which asserts that an empty zebra forces the graph to be bipartite. In the proof of Lemma 2, after deducing that W equals the union of the cycle vertex sets and that each path is a single edge, the paper claims: 'any edge in EC should be followed by an edge in EP' and vice versa, so every face has even length. This claim is false for uncolored faces enclosed by internal cycles C_i: their boundaries are exactly the cycle edges, so consecutive edges are both in EC. A concrete witness is the cube graph with the bottom face chosen as outer. Assign coefficients +1 to the front and back faces, -1 to the left and right faces, and 0 to the top face. At every vertex the sum of incident face coefficients is 0 in F3, so this is a nonzero linear combination with empty support, i.e., an empty zebra with nonempty body. The top face is an internal face bounded entirely by the top cycle, all of whose edges belong to EC, contradicting the claimed alternation. The lemma is likely repairable: faces inside the zebra body do alternate between EC and EP, and each internal hole is bounded by one cycle C_i whose length is even because W contains all its vertices and the number of path endpoints on C_i is even. But as written, the proof is incorrect, and since Theorem 2's rank assertion rests on Lemma 2, the central geometric proof is not fully rigorous.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies Heawood's 1898 spin formulation of Tait colorings of planar cubic graphs. For a simple biconnected planar cubic graph with 2n vertices, the author sets up a homogeneous linear system over F3 whose n+1 internal face equations express that each face is 'proper'. A defining set of vertices is one whose spin values determine all others; free variables of the system provide such sets. The paper introduces 'zebra' sets, which are claimed to be exactly the supports of row combinations of the face equations (Lemma 1). Lemma 2 asserts that an empty zebra implies the graph is bipartite. From these, Theorem 2 concludes that for non-bipartite graphs the rank of the system is n+1, that a set of variables is dependent precisely when its index set contains a zebra, and that any n variables are dependent. Theorem 3 and Corollary 1 derive the existence of defining sets of size n-1 and the bound χ'_3(G) ≤ 3·2^{n-1}, improving Karpov's 9·2^{n-2}. The paper also computes the number of Tait colorings of circular ladder graphs CL_n as 2^n+8 (even n) and 2^n-2 (odd n).","tokens_in":10581,"tokens_out":35234,"duration_ms":301900,"significance":"Assuming the geometric lemmas are made fully rigorous, the paper gives a self-contained proof of the classical rank result and a new upper bound on the number of Tait colorings that is a factor of 1.5 better than Karpov's bound. The bound is not expected to be tight; the exact CL_n computation provides a useful benchmark (roughly 2^n versus 3·2^{n-1}). The zebra characterization of defining sets, if fully established, gives a geometric tool for studying minimal defining sets. The central rank theorem is not new (it is attributed to Heawood and Belaga), so the novelty lies in the geometric proof and the defining-set consequences. The paper is clearly written overall, but the proof of Lemma 2 has a concrete gap that must be repaired before the main theorem can be considered proven.","major_comments":[{"comment":"The proof of Lemma 2 contains a false alternation claim. After establishing that W = ∪ V(C_i) and that each path P_j is a single edge, the text says: 'any edge eC in EC should be followed by an edge eP in EP' and vice versa, so every face has even length. This is not true for faces enclosed by the internal cycles C_i: their boundaries consist entirely of EC edges, so consecutive boundary edges are both in EC. The same applies to the face outside C0. A concrete witness is the cube graph with the bottom face chosen as outer: assigning coefficient +1 to the front and back faces, -1 to the left and right faces, and 0 to the top face gives a nonzero row combination of the main SLE with empty support (an empty zebra), and the top face is an internal face bounded entirely by EC edges. Since Lemma 2 is used to prove Theorem 2's rank assertion for non-bipartite graphs, this gap is load-bearing. The lemma is repairable: for each internal cycle C_i, the length is even because V(C_i) ⊆ W and |W ∩ V(C_i)| is even, and for faces lying in the zebra body the alternation argument does hold, so every face of G has even length and G is bipartite. I recommend that the proof be revised accordingly.","section":"Section 2.3, Lemma 2"}],"minor_comments":[{"comment":"The second assertion of Theorem 2 ('Variables in a certain set are linearly dependent if and only if...') is not defined in the paper, and its proof is dismissed as 'evident'. If 'linearly dependent' means linear dependence of the coordinate functions on the solution space of the main SLE, then the equivalence follows from Lemma 1 by taking supports of row combinations; I suggest defining this notion explicitly and adding the short argument, so that a reader who interprets dependence as column dependence of the SLE matrix is not led astray.","section":"Theorem 2"},{"comment":"There is a textual error in the sentence 'the number of vertices in sets W ∩ V(Ci), i = 0, . . . , k m is even' — the symbol 'm' appears to be a stray remnant, and the intended meaning is that each of the numbers |W ∩ V(Ci)| is even.","section":"Section 2.3, Lemma 2 proof"},{"comment":"The sentence 'The graph CL3 ... illustrates the fact that the estimate χ'_3(G) ≤ 3·2^{n-1} is exact for any n' is misleading, since for CL3 the bound gives 12 while the actual number of Tait colorings is 6. It would be clearer to state that the bound is sharp only up to a constant factor (CL_n gives roughly 2^n while the bound is 3·2^{n-1}).","section":"Conclusion"},{"comment":"The claim that computer calculations show the maximum of χ'_3(G) for fixed 2n vertices is attained by CL_n should be qualified as applying to the planar class and/or to small n, especially in view of the final Remark citing Ivanov's result that for odd n the maximum over all cubic graphs is attained by the non-planar Möbius ladder M_{2n}.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The main result of this paper is plausible and the gap in Lemma 2 appears repairable in a few lines. The rank theorem itself is classic, so the paper's contribution is the geometric proof and the improved counting bound. I recommend revision rather than rejection. The refereeing process would benefit from the authors clarifying the definition of linear dependence of variables in Theorem 2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is the zebra machinery and the bound 3·2^{n−1}; the circular ladder count is already Ivanov's, and the author knows it. The main proof has a gap in Lemma 2, but the lemma looks true and repairable, so the substance survives.\n\nWhat the paper does well: the zebra description of supports is a clean geometric way to think about linear combinations of face equations. It gives a plausible geometric proof of the classical rank n+1 for non-bipartite planar cubic graphs and, as a byproduct, improves Karpov's bound by a factor of 1.5. The CL_3 example is worked out in helpful detail. The closing Remark is candid about Ivanov's prior calculation of χ'_3(CL_n) and the Möbius ladder maximum; I believe the self-disclosure is honest.\n\nNow the soft spots. The proof of Lemma 2 claims that in any face an EC edge must be followed by an EP edge and vice versa. That is false for faces enclosed by an internal cycle: their boundary is all EC. The cube with the bottom face as outer and coefficients +1 on front/back, −1 on left/right, 0 on top gives a nonzero linear combination with empty support; the top face is an internal face bounded only by EC edges. The lemma's conclusion still holds for the cube, since it is bipartite, and the fix looks straightforward: holes are bounded by even cycles because W contains all their vertices, while faces in the zebra body do alternate. But as written, that proof step is wrong, and since Theorem 2 leans on Lemma 2, the central geometric argument needs repair before the paper is referee-ready. Also, the abstract presents the CL_n count as if new; only the Remark discloses Ivanov. That is awkward framing, though not deceptive. The improved bound is modest and the author says so.\n\nBottom line: this paper is for people working on Heawood systems, defining sets, or upper bounds on Tait colorings. The zebra viewpoint is worth engaging, and the paper deserves peer review with a request to fix Lemma 2 and to move the Ivanov acknowledgment into the introduction. I would not cite it myself in the next year, but I would send it to a referee who knows the Heawood literature.","headline":"A nice new proof device and a modest improvement over Karpov, but the main geometric proof has a repairable gap and the headline circular-ladder count is already Ivanov's.","tokens_in":11131,"tokens_out":4857,"would_cite":false,"duration_ms":43851,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C15","05C31"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every non-bipartite simple biconnected planar cubic graph, the internal-face spin equations are linearly independent, capping Tait colorings at $3\\cdot 2^{n-1}$.","keywords":["cubic graph","Tait coloring","Heawood vector","defining vertex set","zebra","rank over F3","circular ladder graph","planar graph"],"falsifier":"Take any non-bipartite simple biconnected planar cubic graph, for instance the circular ladder $CL_5$, and perform Gaussian elimination over $\\mathbb{F}_3$ on the internal-face equations: the matrix must have rank $n+1$ (for $CL_5$, rank $6$). If any such graph yields a rank smaller than $n+1$—equivalently, if a nontrivial linear combination of internal-face equations sums to zero—the theorem fails.","tokens_in":10090,"feed_emoji":"🎨","tokens_out":15306,"duration_ms":118518,"temperature":0.7,"pith_summary":"This paper proves that the linear equations enforcing Heawood's face-propriety condition—the sum of vertex spins on every internal face is zero modulo $3$—are always independent for a non-bipartite (odd-cycle-containing) simple biconnected planar cubic graph. With $2n$ vertices there are $n+1$ such equations, so the solution space has dimension $n-1$; this means values on any $n-1$ vertices determine the remaining spins of any Heawood vector. Because Tait-coloring classes are in bijection with Heawood vectors, the paper obtains an upper bound of $3\\cdot 2^{n-1}$ on the number of Tait colorings, half the previous general bound. It also computes the exact Tait-coloring count for circular ladder graphs, confirming that the general bound cannot be improved by more than a factor of two without additional information.","feed_headline":"Tait colorings capped at 3·2^(n−1)","feed_subtitle":"Rank n+1 proof: n−1 vertex spins decide all the rest, halving the old upper bound","key_machinery":"The load-bearing object is the 'zebra'. A zebra is a vertex set formed by choosing an outer cycle, optionally several disjoint cycles inside it, and disjoint paths with an even number of endpoints on these cycles; the zebra is the set of all cycle and path vertices except those chosen endpoints. The paper proves two structural facts: every support of a linear combination of internal-face equations is a union of zebras with disjoint bodies, and a zebra can be empty only if the graph is bipartite. These two facts carry the entire rank argument, because a linear dependence among the $n+1$ equations would be a nonzero combination whose support is empty—an empty zebra—forcing bipartiteness, the one case excluded by the theorem.","core_discovery":"The central discovery is that the Heawood system has full rank in exactly the cases that matter for the Four-Color problem. For a simple biconnected planar cubic graph with $2n$ vertices, the paper defines spins $\\sigma(v)\\in\\{+1,-1\\}$ and calls a face proper when the sum of its vertex spins is $0$ in $\\mathbb{F}_3$. A Tait coloring is, up to a global cyclic shift of the three colors, the same as a Heawood vector: a spin assignment making every face proper. Theorem 2 states that for non-bipartite $G$ the $n+1$ equations for internal faces are linearly independent over $\\mathbb{F}_3$, hence rank $n+1$; the bipartite case is the sole exception, with rank $n$. The proof is geometric: the support of any linear combination of face equations must be a union of 'zebra' vertex sets built from cycles and paths, and an empty zebra can occur only in a bipartite graph. Since a nontrivial dependence would have empty support, none exists. This yields defining sets of $n-1$ vertices and the bound $\\chi'_3(G)\\le 3\\cdot 2^{n-1}$; Theorem 4 gives the exact counts $2^n+8$ and $2^n-2$ for circular ladder graphs with even and odd $n$.","pith_inferences":["The zebra support criterion could be read algorithmically: to test whether a proposed defining set is minimal, one can look directly for a zebra contained in it, without first solving the linear system; the paper uses the criterion only to prove non-minimality, not to search.","The exact ladder counts suggest the general bound $3\\cdot 2^{n-1}$ is far from tight for large families; a natural next step, left implicit, is to relate the gap to the size $m(G)$ of the smallest defining set, since the paper's own conclusion notes the sharper bound that would follow.","Because the only obstacle to treating the spin system as an ordinary linear problem is the requirement that every coordinate be nonzero, a Fourier or $\\alpha$-representation evaluation of the face constraints, as floated at the end of the paper, could yield exact counts for wider graph classes than circular ladders."],"forward_implications":["For every non-bipartite simple biconnected planar cubic graph there exists a defining set of $n-1$ vertices, so the number of Heawood vectors is at most $2^{n-1}$ and the number of Tait colorings at most $3\\cdot 2^{n-1}$.","Any $n$-vertex set in such a graph contains a zebra and therefore is not a minimal defining set; minimal defining sets must have fewer than $n$ vertices.","In the bipartite case the rank drops to $n$, exactly the case where an empty zebra can occur; bipartiteness is the unique obstruction to the full-rank conclusion.","For circular ladder graphs the exact counts $2^n+8$ (even $n$) and $2^n-2$ (odd $n$) show that the general upper bound has the right exponential order but leaves room for improvement of at most a factor of two without further hypotheses.","Knowing the size $m(G)$ of a minimal defining set would give the sharper bound $\\chi'_3(G)\\le 3\\cdot 2^{m(G)}$, as the paper notes in its conclusion."],"supporting_citations":[{"why":"Supplies the classical equivalence between Tait-coloring classes and spin assignments whose face sums vanish modulo $3$, the foundation of the whole approach.","marker":"[1]"},{"why":"Provides the planar-graph and radial-graph background, including the four-color setting, used in the proof of the Heawood correspondence.","marker":"[2]"},{"why":"Develops the Heawood-vector framework and the rank dichotomy between bipartite and non-bipartite graphs that Theorem 2 reproves geometrically.","marker":"[3]"},{"why":"Introduces defining sets and gives the previous bound $9\\cdot 2^{n-2}$ that Corollary 1 improves by a factor of two.","marker":"[8]"},{"why":"Supplies the theory of everywhere-nonzero $3$-flows and dual vertex colorings used to discuss the bipartite exceptional case.","marker":"[9]"},{"why":"Establishes the duality between proper colorings and nonzero flows that underlies the proof of Theorem 1.","marker":"[10]"},{"why":"Provides known exact counts for circular and related ladder graphs against which Theorem 4's exact values are compared.","marker":"[12]"}],"fun_headline_variants":["Heawood spin system: rank n+1, defining sets of n-1","Full-rank spin system halves Tait coloring bound","Tait colorings: n-1 vertex spins decide all the rest","Geometric proof: Heawood equations always independent","Exact Tait counts for circular ladders: 2^n±2"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire rank theorem rests on the geometric claim that any linear dependence among face equations has a support built from 'zebra' patterns—cycles and paths with an even number of endpoints—and that an empty zebra can occur only in a bipartite graph; a dependence not fitting that description would allow the rank to be smaller than $n+1$.","fun_headline_variants_meta":{"raw":{"variants":["Heawood spin system: rank n+1, defining sets of n-1","Full-rank spin system halves Tait coloring bound","Tait colorings: n-1 vertex spins decide all the rest","Geometric proof: Heawood equations always independent","Exact Tait counts for circular ladders: 2^n±2"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000567,"raw_usage":{"total_tokens":2811,"prompt_tokens":1193,"completion_tokens":1618,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":809,"completion_tokens_details":{"reasoning_tokens":1527}},"tokens_in":809,"tokens_out":1618,"duration_ms":11824,"temperature":1.0,"reasoning_tokens":1527,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:40:14.318481+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any non-bipartite simple biconnected planar cubic graph, for instance the circular ladder $CL_5$, and perform Gaussian elimination over $\\mathbb{F}_3$ on the internal-face equations: the matrix must have rank $n+1$ (for $CL_5$, rank $6$). If any such graph yields a rank smaller than $n+1$—equivalently, if a nontrivial linear combination of internal-face equations sums to zero—the theorem fails.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the classical equivalence between Tait-coloring classes and spin assignments whose face sums vanish modulo $3$, the foundation of the whole approach."},{"cited_title":"Ore, The Four-Color Problem","cited_arxiv_id":null,"evidence_quote":"Provides the planar-graph and radial-graph background, including the four-color setting, used in the proof of the Heawood correspondence."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Develops the Heawood-vector framework and the rank dichotomy between bipartite and non-bipartite graphs that Theorem 2 reproves geometrically."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces defining sets and gives the previous bound $9\\cdot 2^{n-2}$ that Corollary 1 improves by a factor of two."},{"cited_title":"Diestel, Graph Theory","cited_arxiv_id":null,"evidence_quote":"Supplies the theory of everywhere-nonzero $3$-flows and dual vertex colorings used to discuss the bipartite exceptional case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the duality between proper colorings and nonzero flows that underlies the proof of Theorem 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides known exact counts for circular and related ladder graphs against which Theorem 4's exact values are compared."}],"review_version":1}