The Heawood approach to Tait colorings and defining vertex sets

E. Yu. Lerner

REVIEW 1 major objections 4 minor 12 references

The Heawood approach to Tait colorings and defining vertex sets

T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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}$.

desk verdict 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. read the letter →

arxiv 2411.15992 v1 pith:P6RORCZV submitted 2024-11-24 math.CO

E. Yu. Lerner This is my paper · ORCID

classification math.CO MSC 05C1005C1505C31

keywords cubicgraphTaitcoloringHeawoodvectordefiningvertexsetzebrarankoverF3circularladderplanar

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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.

Desk Editor's Note

read the 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.

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

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

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

Referee Report

1 major / 4 minor

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

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 (1)

[Section 2.3, Lemma 2] 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.

minor comments (4)

[Theorem 2] 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 2.3, Lemma 2 proof] 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.
[Conclusion] 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}).
[Introduction] 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}.

Circularity Check

0 steps flagged · score 1.0 of 10

No meaningful circularity: the rank theorem and counting corollary are derived from definitions, standard duality, and a geometric support characterization; the sole self-citation [11] is a non-load-bearing future-work remark.

full rationale

The central claim (Theorem 2: rank = n+1 for non-bipartite graphs) follows from Lemma 1 and Lemma 2. Lemma 1 is a direct geometric description of supports of linear combinations of the face equations, derived from the SLE and planarity rather than from the theorem's conclusion. Lemma 2 is an independent combinatorial claim about empty zebras implying bipartiteness; however questionable its proof step about EC/EP alternation may be, that is a correctness gap, not circularity. Corollary 1 is then a straightforward counting consequence: n-1 free variables give at most 2^{n-1} Heawood vectors, multiplied by 3 by Theorem 1. Theorem 1 is proved using standard, external facts: Tutte's coloring/flow duality [10] and Ore's double (radial) graph construction [2]; no result of this paper is assumed. The only self-citation is reference [11] (Kuptsov, Lerner, Mukhamedjanova), cited in the Conclusion merely as a possible future Fourier/alpha-representation direction; it plays no role in any proof or in the bound. Thus no fitted input is renamed as a prediction, no theorem is imported from the authors' prior work, and no definition encodes the target result. The improvement over Karpov's bound is an external comparison, not a circular input.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper introduces no free parameters: every constant is structural, such as the number of vertices, faces, and the ±1 coefficients in F3. The proofs rely only on standard graph theory facts and on the paper's own zebra definition, which is a new combinatorial construct rather than an empirically fitted entity.

assumptions (4)

standard math Tutte's duality: proper k-colorings of a plane graph correspond to nowhere-zero k-flows in the dual graph.
Invoked in the proof of Theorem 1 to connect Tait colorings of the medial graph with flows on the double graph.
standard math Euler's formula and cubic plane incidence: a plane cubic graph on 2n vertices has n+2 faces, and each vertex lies on exactly three faces.
Determines the number of equations and variables in the SLE and justifies the all-ones cancellation used to define the main SLE in Section 1.
standard math The all-ones combination of all face equations vanishes, so one face equation is redundant and the internal-face system is the main object.
Used in Section 1 to reduce the n+2 face equations to n+1 internal-face equations.
domain assumption Simple, biconnected, planar, cubic is the class of graphs studied.
All theorems and the Heawood correspondence are stated for this class in Section 1.

invented entities (1)

zebra
purpose: A vertex set defined from cycles and paths that characterizes which variables can be cancelled in a linear combination of the Heawood face equations.
The zebra is a new combinatorial-geometric definition introduced in Section 2.2. It has no falsifiable handle outside the paper; its validity is established by the proofs of Lemmas 1 and 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Heawood approach to Tait colorings and defining vertex sets." pith.science (2026). https://pith.science/paper/P6RORCZV

@misc{pith2026241115992,
  author       = {Pith},
  title        = {Pith review of: The Heawood approach to Tait colorings and defining vertex sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P6RORCZV}},
  note         = {Machine review of arXiv:2411.15992}
}

abstract

Given a simple biconnected planar cubic graph, we associate each its vertex among $2n$ ones with the so-called spin, i.e., a variable which takes on values $\pm 1$. P. J. Heawood has proved that a Tait coloring, accurate to the choice of a color for one edge, is equivalent to the choice of spin values so as to make the sum of these value at vertices of any face be a multiple of~3. We treat faces, which satisfy this condition, as {\it proper}. The condition that guarantee the propriety of faces define a system of linear equations (SLE) with respect to variables, which take on nonzero values in the field ${\mathbb F}_3$. We say that a set of vertices is {\it defining} if values of spins of these vertices uniquely define values of the rest spins. In particular, so is the set of vertices which correspond to all free variables of the SLE. We actualize the approach proposed by P. J. Heawood by proposing a geometric proof of the fact that for a non-bipartite graph the rank of the SLE equals $n+1$. Moreover, we also geometrically describe the necessary condition for the minimality of the defining set. This implies that in the case of a non-bipartite graph there exist defining subsets consisting of $n-1$ vertices. As a simple corollary, we conclude that the number of Tait colorings in this case does not exceed $3\cdot 2^{n-1}$. Though this estimate is not exact, it is by half better than the known one. We also prove that the number of Tait colorings for a graph $CL_n$, which is bipartite for even $n$ and non-bipartite for an odd one, equals $2^n+8$ and $2^n-2$, correspondingly.

Figures

Figures reproduced from arXiv: 2411.15992 by the authors.

**Figure 1.** The graph CL3 and its faces. One can easily prove that for this graph there exist two Heawood vectors (σ(1), . . . , σ(6)) = (1, 1, 1, −1, −1, −1) and (−1, −1, −1, 1, 1, 1). These two vectors correspond to two classes of Tait colorings. In the first case, numbers of colors 0, 1, 2 ∈ F3 of edges, which are incident to vertices 1, 2, 3, increase by 1 when bypassing counterclockwise. At the same time, colors of edges, … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

P. J. Heawood, On the four-colour map theorem. — Quart. J. Pure Appl. Math. 29 (1898) 270–285

work page
[2]

Ore, The Four-Color Problem

O. Ore, The Four-Color Problem. Academic Press, New York and London, 1967

work page 1967
[3]

E. G. Belaga, On Heawood vectors of pseudotriangulations. — Soviet Math. Dokl. 17:6 (1976) 1494–1498

work page 1976
[4]

E. G. Belaga, Mod 3 arithmetic on triangulated Riemann surfaces. — The- oretical Computer Science 263 (2001) 123–137

work page 2001
[5]

Yu. V. Matiyasevich, A criterion for vertex colorability of a graph stated in terms of edge orientations. — Diskretnyi Analiz, issue 26 (1974) 65–71 (in Russian), https://arxiv.org/abs/0712.1884 (in English)

work page Pith review arXiv 1974
[6]

Yu. V. Matiyasevich, Problem 21. — Combinatorial Asymptotical Analisys 2, Krasnoyarskii State University, Krasnoyarsk (1977) 178–179 (in Rus- sian)

work page 1977
[7]

Yu. V. Matiyasevich, Some algebraic methods for calculating the number of colorings of a graph. — Journal of Mathematical Sciences 121 (2004) 2401–2408

work page 2004
[8]

D. V. Karpov, On Proper Edge 3-Colorings of a Cubic Graph. — Journal of Mathematical Science 255 (2021) 17–27

work page 2021

Show all 12 references

[9]

Diestel, Graph Theory

R. Diestel, Graph Theory. Springer, 2024

2024
[10]

W. T. Tutte, A contribution to the theory of chromatic polynomials — Can. J. Math. 6 (1953) 80–91

1953
[11]

A. P. Kuptsov, E. Yu. Lerner, S. A. Mukhamedjanova, Flow polynomials as Feynman amplitudes and their α -representation — Electron. J. Combin. 24 (2017) no. 1, 19 pp

2017
[12]

M. P. Ivanov, An exact bound on the number of proper 3-edge-colorings of a connected cubic graph. — Journal of Mathematical Sciences 275 (2023) 130–146. 12

2023

Pith tools

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

[1] [1]

P. J. Heawood, On the four-colour map theorem. — Quart. J. Pure Appl. Math. 29 (1898) 270–285

work page

[2] [2]

Ore, The Four-Color Problem

O. Ore, The Four-Color Problem. Academic Press, New York and London, 1967

work page 1967

[3] [3]

E. G. Belaga, On Heawood vectors of pseudotriangulations. — Soviet Math. Dokl. 17:6 (1976) 1494–1498

work page 1976

[4] [4]

E. G. Belaga, Mod 3 arithmetic on triangulated Riemann surfaces. — The- oretical Computer Science 263 (2001) 123–137

work page 2001

[5] [5]

Yu. V. Matiyasevich, A criterion for vertex colorability of a graph stated in terms of edge orientations. — Diskretnyi Analiz, issue 26 (1974) 65–71 (in Russian), https://arxiv.org/abs/0712.1884 (in English)

work page Pith review arXiv 1974

[6] [6]

Yu. V. Matiyasevich, Problem 21. — Combinatorial Asymptotical Analisys 2, Krasnoyarskii State University, Krasnoyarsk (1977) 178–179 (in Rus- sian)

work page 1977

[7] [7]

Yu. V. Matiyasevich, Some algebraic methods for calculating the number of colorings of a graph. — Journal of Mathematical Sciences 121 (2004) 2401–2408

work page 2004

[8] [8]

D. V. Karpov, On Proper Edge 3-Colorings of a Cubic Graph. — Journal of Mathematical Science 255 (2021) 17–27

work page 2021