REVIEW 2 major objections 3 minor 5 references
Planar cubic graphs of small diameter
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper builds an infinite family of cubic planar graphs whose faces have length at most 7 and whose diameter grows logarithmically with vertex count, refuting the suspicion that bounded face length forces diameter at least a constant…
desk verdict A real counterexample to the bounded-face diameter suspicion, but the stated diameter bound is false as written and needs a corrected constant (4k-4 instead of 3k). read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the graph family $\{G_k\}$: take two copies of a ternary tree of height $k$, identify the leaves pairwise, subdivide every edge that is not incident to a leaf or root, then add an edge between consecutive vertices at each even depth, cyclically. The mechanism behind the claimed small diameter is the combination of the two tree trunks, which put every vertex within $k$ steps of one of the two roots, and the added same-depth edges, which give short lateral moves across each level. The face-length analysis is local: faces are checked around each tree vertex and come out as 4-, 5-, 6-, or 7-cycles.
What would settle it
Compute the distance between the two roots of $G_k$ by breadth-first search on the explicit drawing for $k = 2, 3, 4$; the claimed diameter bound requires this distance to be at most $3k$. Comparing the measured diameter of $G_k$ with $3 \log_2 n$ for a range of $k$ settles whether the central claim holds.
Extended reading notes
Core claim
The central claim is that the family $\{G_k\}_{k \ge 2}$ consists of cubic planar graphs with all faces of length 4, 5, 6, or 7, and with diameter at most $3k$. Since $G_k$ has at least $2^k$ vertices, this yields diameter $O(\log n)$. Each $G_k$ is built from two copies of a complete rooted ternary tree of height $k$: the copies are glued by identifying corresponding leaves, every edge not incident to a leaf or a root is subdivided, and then for each tree and each even depth $d$ with $2 \le d \le 2k - 2$, consecutive vertices at that depth are joined cyclically by new edges. The paper asserts that these added edges preserve planarity, that every vertex ends with degree 3, and that the resulting faces have lengths only 4, 5, 6, or 7. The diameter bound is stated directly, and the surrounding argument is the construction itself.
Load-bearing premise
The load-bearing premise is that every two vertices of $G_k$ are at distance at most $3k$; the paper states this in one sentence without derivation, and the $O(\log n)$ diameter conclusion rests entirely on it.
Editorial extensions
If this is right
- The face-length threshold is sharp: cubic planar graphs with all faces of length at most 6 have diameter $\Omega(\sqrt{n})$, while the new family has faces of length at most 7 and logarithmic diameter.
- Because $n \ge 2^k$ and diameter is at most $3k$, the family has diameter at most $3 \log_2 n$, an explicit logarithmic upper bound.
- The graphs $G_k$ are explicit and easily drawn, so they give concrete small-diameter examples in the regime between fullerenes (face length 5–6) and general cubic planar graphs.
- The construction resolves the open question that motivated it: bounded face length alone does not force polynomial diameter in cubic planar graphs.
Reading between the lines
- The 6-versus-7 threshold suggests that the square-root obstruction is tied to the absence of faces longer than 6; isolating exactly which local configurations force long distances would clarify why fullerenes are necessarily large-diameter.
- The two-glued-trees template is modular: varying the branching factor or the height of the trees, or the spacing of the added depth edges, could plausibly produce cubic planar graphs with bounded faces and diameter interpolating between $\log n$ and $\sqrt{n}$.
- The paper does not discuss vertex connectivity; checking whether $G_k$ is 3-connected, and if not, whether a 3-connected variant with the same diameter and face-length bounds exists, would tie the construction more closely to fullerene-like models.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an explicit family {G_k} of planar graphs intended to be cubic, with all faces of length at most 7 and diameter O(log n). The construction starts from a rooted tree T_k whose root has degree 3, every other internal vertex has degree 3, and all leaves are at distance k; two copies are glued along their leaves, all edges except those incident to leaves or roots are subdivided, and then perfect matchings are added on the sets of vertices at each even distance from the root. The authors claim this refutes the suspicion that cubic planar graphs with bounded face length must have diameter in Ω(√n).
Significance. If the construction and the diameter bound were correct, this would be a clean and surprising counterexample to a plausible conjecture, and the paper would be a useful short contribution. The construction has no fitted parameters and is concrete enough to check; the face-length census is plausible. I also note that the parity objection based on 3^k leaves does not apply: since non-root internal vertices of T_k have two children and the root has three, the number of leaves is 3·2^{k−1}, which is even. However, the proof of the central diameter claim is invalid as written, and the definition of the added edges has an ambiguity at the leaf level. The O(log n) conclusion may well be salvageable with a corrected constant and a real proof, but the present manuscript does not establish it.
major comments (2)
- [Last paragraph (diameter claim)] The assertion that every two vertices of G_k are at distance at most 3k is false. In each copy of T_k, the distance from the root to any leaf is exactly 2k−2: the root-to-leaf path has k tree edges, of which all except the first and last are subdivided. After gluing, the two copies intersect only at the leaves, so the distance between the two roots is at least (2k−2)+(2k−2)=4k−4, and a path of this length exists. For k≥5, 4k−4>3k, so the stated bound is contradicted. Since this single sentence is the only argument for the O(log n) claim, the main theorem is not established as written. A corrected bound such as 4k−4, if proved, would still give O(log n) because |V(G_k)|=Θ(2^k).
- [Definition of G_k (matching step)] The construction of the added edges at distance d=2k−2 (the leaves) needs clarification. The leaves are identified when the two copies are glued, so the ordered list v0,…,v_l at distance 2k−2 is the same vertex set for both trees. The phrase 'for each of the two trees' would therefore add the same perfect matching twice, giving each leaf two added incidences, or parallel edges, which contradicts the statement that each degree-2 vertex 'got one new incident edge'. The cubic property requires that the leaf matching be added only once. Please state this explicitly, for example by defining the matching on the union's vertices at each even level rather than separately for the two trees.
minor comments (3)
- [Last paragraph] The inequality 'n ≥ 2k' should read 'n ≥ 2^k'; the exponent appears to be missing.
- [Last paragraph] The base of the logarithm in '3 log(n)' should be specified; the argument requires log base 2, so it should be written as log_2 n.
- [Definition of G_k] The sentence 'Note that 𝓁 is odd as d≥2' is correct because the number of vertices at each relevant even level is even, but the wording is confusing: 𝓁 is the last index, so the reader may think the number of vertices is odd. Consider saying explicitly that the number of vertices at level d is even and hence a perfect matching exists.
Circularity Check
The construction is self-contained and no claim reduces to its inputs by construction.
full rationale
The paper defines the family {G_k} directly from rooted ternary trees, subdivisions, and explicit edge additions. There are no fitted parameters, no calibrated constants, and no quantity is defined in terms of the target diameter bound. The lower-bound result for fullerene graphs is cited as background motivation, not as an input to the construction, and the final mention of Nicodemos and Stehlík is a remark, not a load-bearing step. The central claim—that G_k is cubic, planar, has faces of length at most 7, and has O(log n) diameter—is argued from the explicit definition with a figure and a face-length analysis. Even if the parity objection or the diameter estimate were mathematically incorrect, that would be a correctness flaw, not circularity, because the claims are not assumed but asserted and derived. No self-citation chain is used to forbid alternatives or to justify the ansatz, and no known result is merely renamed. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption The drawing of G_k described in the construction is planar.
- domain assumption Every face of G_k has length at most 7.
- ad hoc to paper The diameter of G_k is at most 3k.
Cite this review
Pith. "Pith review of Planar cubic graphs of small diameter." pith.science (2026). https://pith.science/paper/IDSF7ZFC
@misc{pith2026190805481,
author = {Pith},
title = {Pith review of: Planar cubic graphs of small diameter},
year = {2026},
howpublished = {\url{https://pith.science/paper/IDSF7ZFC}},
note = {Machine review of arXiv:1908.05481}
}
abstract
Cubic planar $n$-vertex graphs with faces of length at most $6$, e.g., fullerene graphs, have diameter in $\Omega(\sqrt{n})$. It has been suspected, that a similar result can be shown for cubic planar graphs with faces of bounded length. This note provides a family of cubic planar $n$-vertex graphs with faces of length at most $7$ and diameter in ${O}(\log n)$, thus refuting the above suspicion.
Figures
Reference graph
Works this paper leans on
-
[1]
V. Andova , T. Do s li\'c , M. Krnc , B. Lu z ar , and R. S krekovski , On the diameter and some related invariants of fullerene graphs. , MATCH Commun. Math. Comput. Chem. , 68 (2012), pp. 109--130
work page 2012
-
[2]
V. Andova , F. Kardo s , and R. S krekovski , Mathematical aspects of fullerenes. , Ars Math. Contemp. , 11 (2016), pp. 353--379
work page 2016
-
[3]
D. Nicodemos and M. Stehl \' k , Fullerene graphs of small diameter , MATCH Commun. Math. Comput. Chem., 77 (2017), pp. 725--728
work page 2017
-
[4]
P. Schwerdtfeger, L. N. Wirz, and J. Avery , The topology of fullerenes , Wiley Interdisciplinary Reviews: Computational Molecular Science, 5 (2015), pp. 96--145
work page 2015
-
[5]
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTION or pop #1 'skip if FUNCTION new.block.checka empty 'skip 'new.block if FUNCTION field.or.null duplicate empty pop "" 'skip ...
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.