{"id":"67da1484-67d1-4e45-a652-8fad379211cd","arxiv_id":"1908.05481","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Knauer and Micek build cubic planar graphs with faces of length at most 7 and diameter O(log n), disproving the suspected square-root lower bound for bounded-face cubic planar graphs.","lead":"This paper constructs a family of cubic planar graphs with faces of length at most 7 whose diameter grows only logarithmically with the number of vertices. The construction refutes the suspicion that bounded face length forces a square-root lower bound on diameter.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The construction is not cubic: G_k has 3^k shared leaves (odd), so the required added edges cannot give each leaf exactly one new incident edge; the central claim fails already at the definition stage.","rationale":"The reader's conditional verdict focused on the unsupported and apparently false diameter bound 3k. That concern is legitimate: the two roots are at distance at least 4k-4, so the stated bound is wrong, and the paper supplies no correct proof of the O(log n) diameter. However, before the diameter can even be discussed, the graph must be cubic. The construction as written cannot be cubic because the shared leaf set has odd size 3^k, making a perfect matching of added leaf edges impossible, and the total vertex count is odd. This is not a missing proof or a constant error; the object constructed is not of the claimed type. Therefore the central theorem, as stated, is invalid. The asymptotic idea might be salvageable by modifying the underlying tree so that the leaf count is even and by supplying a correct diameter proof, but the paper as written does not do so. Hence the verdict should move from CONDITIONAL to REJECT.","tokens_in":2001,"tokens_out":16414,"duration_ms":165650,"concrete_test":"Instantiate k=2 exactly as described: take two copies of the full ternary tree of height 2 (root with 3 children, each with 3 leaves), identify corresponding leaves, and perform no subdivisions because all edges are incident to a root or a leaf. The resulting graph has 17 vertices and 9 shared leaves, each of degree 2. Try to add edges among the leaves to make every vertex degree 3. Since 9 is odd, any graph on these 9 leaves has an even sum of degrees, so the total added degree contributed to the leaves must be even; making all 9 leaves degree 3 would require added degree 9, an odd number. Hence no added-edge set can make the graph cubic. This single parity check settles that the construction is not cubic.","verdict_should_be":"REJECT","load_bearing_attack":"The paper's central claim is that {G_k} is a family of cubic planar graphs. This fails for parity reasons. In T_k, with the stated root degree 3 and leaves at distance k, the number of leaves is 3^k, which is odd. Gluing two copies by identifying corresponding leaves produces 3^k shared leaf vertices. Before the added edges, each shared leaf has degree exactly 2, coming from one incident tree edge in each copy. To make the graph cubic, the added edges must give every leaf exactly one additional incident edge, i.e., the added edges restricted to leaves must form a perfect matching. A perfect matching on 3^k vertices exists only if 3^k is even, and 3^k is odd for every k. Equivalently, the total number of vertices after gluing is 2*((3^{k+1}-1)/2) - 3^k = 2*3^k - 1, which is odd, while every cubic graph has even order because the sum of degrees is 3n and must be even. For k=2 this is concrete: G_2 would have 17 vertices and 9 shared leaves, so the leaves cannot all receive exactly one new edge. The paper's statement that 'each of them got one new incident edge' is therefore false for the leaves. The diameter issue identified by the reader is real, but it is secondary: the constructed object is not even cubic.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":2243,"tokens_out":22491,"duration_ms":228166,"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":[{"comment":"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).","section":"Last paragraph (diameter claim)"},{"comment":"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.","section":"Definition of G_k (matching step)"}],"minor_comments":[{"comment":"The inequality 'n ≥ 2k' should read 'n ≥ 2^k'; the exponent appears to be missing.","section":"Last paragraph"},{"comment":"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.","section":"Last paragraph"},{"comment":"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.","section":"Definition of G_k"}],"recommendation":"major_revision","confidential_remarks":"The construction is promising and the main idea is likely correct, but the submitted proof of the diameter bound is invalid and the leaf-level matching is under-specified. This is fixable within the paper's scope by replacing 3k with a correct O(k) bound such as 4k−4 and clarifying the matching step, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is my read. The construction is the real thing: an explicit family of planar cubic graphs with face lengths at most 7 and diameter logarithmic in n, which does refute the suspicion that bounded faces force square-root diameter. The idea—two ternary trees glued at their leaves, subdivided, then matched level-wise—is clean and self-contained. The face-length analysis is plausible; the census of 4,5,6,7-faces around root, internal vertices, and leaves matches the figure. There is no curve-fitting or post-hoc tuning.\n\nThe soft spot is exactly where the reader put it. The proof of the upper bound is one sentence: 'every two vertices can be joined by a path of length at most 3k.' That sentence is false. After subdivision, each root is distance 2k−2 from any leaf, and the only connections between the two copies are at the leaves, so the two roots are at distance 4k−4. For k≥5 this is already larger than 3k. So the stated constant 3 is wrong.\n\nThat said, the asymptotic claim still holds. The graph has n = Θ(2^k), and the distance between any two vertices is at most 4k−4 (you can go from either vertex to a leaf in its own copy and across), so the diameter is O(log n). The paper just needs the constant corrected and the argument made explicit. This is a fixable error, not a broken idea.\n\nOne thing I checked because it looked alarming: the stress-test note worries that the tree has 3^k leaves, which is odd, so a perfect matching on the leaves is impossible. But T_k has 3·2^{k−1} leaves—root degree 3, each other internal vertex degree 3, so two children. That count is even, and the level-by-level matching exists. The parity objection does not land.\n\nSo: the paper as submitted has a false statement in the proof, but the main theorem is true and essentially proved by the construction. It deserves a serious referee, and the referee should ask for a corrected diameter bound. A short revision would make this a nice note for people working on diameter bounds in cubic planar graphs.","headline":"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).","tokens_in":2749,"tokens_out":9404,"would_cite":true,"duration_ms":82211,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C12"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["cubic planar graphs","diameter","bounded face length","fullerene graphs","logarithmic diameter","ternary tree construction","planar embeddings","face length threshold"],"falsifier":"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.","tokens_in":1779,"feed_emoji":"📐","tokens_out":11605,"duration_ms":101342,"temperature":0.7,"pith_summary":"Fullerene graphs are cubic planar graphs whose faces are pentagons and hexagons, and their diameter is known to grow at least as a constant times $\\sqrt{n}$. It was suspected that any fixed bound on face length would force the same square-root growth. This paper refutes that suspicion by giving, for every $k \\ge 2$, a cubic planar graph $G_k$ whose faces have length at most 7 and whose diameter is at most $3k \\le 3 \\log_2 n$, with $n = |V(G_k)|$. The construction glues two rooted ternary trees of height $k$ leaf-to-leaf, subdivides the internal edges, and adds edges between vertices at the same depth. If the diameter bound is correct, bounded face length alone does not restrict cubic planar diameter to polynomial growth.","feed_headline":"7-sided faces let cubic planar graphs beat square-root diameter","feed_subtitle":"A new explicit family has faces of length at most 7 yet logarithmic diameter, refuting a suspected lower bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Proves the $\\Omega(\\sqrt{n})$ lower bound for cubic planar graphs with faces of length at most 6 and raises the suspicion the paper refutes.","marker":"[1]"},{"why":"Surveys mathematical aspects of fullerenes that frame the bounded-face diameter problem.","marker":"[2]"},{"why":"Supplies fullerene graphs of diameter $\\sqrt{4n/3}$, the best small-diameter comparison for the new logarithmic family.","marker":"[3]"}],"fun_headline_variants":["Cubic planar graphs with 7-sided faces achieve log diameter","Refuting suspected lower bound: logarithmic diameter in cubic planar graphs","Explicit cubic planar graphs with log diameter and 7-face bound","Cubic planar graphs beat square-root diameter with 7-sided faces"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cubic planar graphs with 7-sided faces achieve log diameter","Refuting suspected lower bound: logarithmic diameter in cubic planar graphs","Explicit cubic planar graphs with log diameter and 7-face bound","Cubic planar graphs beat square-root diameter with 7-sided faces"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00092,"raw_usage":{"total_tokens":3882,"prompt_tokens":814,"completion_tokens":3068,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":2995}},"tokens_in":430,"tokens_out":3068,"duration_ms":21150,"temperature":1.0,"reasoning_tokens":2995,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:13:04.582961+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Andova , T","cited_arxiv_id":null,"evidence_quote":"Proves the $\\Omega(\\sqrt{n})$ lower bound for cubic planar graphs with faces of length at most 6 and raises the suspicion the paper refutes."},{"cited_title":"Andova , F","cited_arxiv_id":null,"evidence_quote":"Surveys mathematical aspects of fullerenes that frame the bounded-face diameter problem."},{"cited_title":"Nicodemos and M","cited_arxiv_id":null,"evidence_quote":"Supplies fullerene graphs of diameter $\\sqrt{4n/3}$, the best small-diameter comparison for the new logarithmic family."}],"review_version":1}