{"id":"b4ed862d-f82f-4a1f-a640-9f7e18a218e2","arxiv_id":"2508.01349","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every polyhedron is classified by its set of pair common-neighbour counts, with a complete trichotomy for every finite set of counts.","lead":"This paper classifies every polyhedron (a 3D solid's network of corners and edges) by the set of numbers of common neighbours shared by any two corners. It gives the complete answer for every possible set of counts: a full list of the shapes, infinitely many shapes, or none.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Completeness of Theorem 1.3 hinges on an unshipped computer enumeration of all triangulations up to 12 vertices; a single missed graph would invalidate the trichotomy.","rationale":"The central trichotomy has two halves: classification/nonexistence for all A and construction of infinite families. The constructions (Propositions 6.1-6.3) are supported by shipped code for 6.1 and 6.2 and by a plausible gluing argument for 6.3; the bounded-exception bounds follow from Lemma 3.5 together with the cited external domination theorem. The one step that is not reproducible from the text is the finite enumeration in Section 2. Tracing dependencies: Theorem 1.3 gives Table 1; Corollary 4.7 uses Table 1 to exclude the tetrahedron, cube, and icosahedron; Proposition 5.2 uses Lemma 3.1, Lemma 3.6, and Proposition 5.1 to prove that Table 2 is complete. Every branch of Proposition 5.2 ultimately relies on the completeness of Theorem 1.3, so a flaw in the enumeration is fatal to the 'no other types' promise. The reader's conditional verdict is therefore appropriate: independent reproduction of the enumeration would upgrade confidence, while failure would overturn the classification. I did not find an internal algebraic contradiction in the hand-written parts, although some planar-geometry steps (for instance, the first paragraph of Section 2 and parts of Proposition 5.1) are asserted rather than fully formalised.","tokens_in":18516,"tokens_out":21639,"duration_ms":254133,"concrete_test":"Regenerate the enumeration independently: generate all 3-connected plane triangulations on n = 4,...,12 vertices using plantri (for example, plantri -g -c3 -m3 -M12 n, or the equivalent via nauty), compute A(G) for each graph, and retain exactly those with 1 not-in A. Compare the resulting set with the list implied by Table 1: the cube, all bipyramids, T_l for 2 <= l <= 10, S5, S6, S7, and S2, S3, S4, S8, S9, S10. Also compute A(G) for each of the ten graphs in Figure 2 and check it matches the Table 1 entry. If the generated set matches precisely and every type entry is correct, the load-bearing doubt is resolved. If any extra or missing graph appears, or any type entry differs, Theorem 1.3 is false and the classification needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 reduces the 1-not-in-A case for triangulations with Delta <= 5 to the degree bound p <= 12, and then states: 'We inspected all triangulations with up to 12 vertices (code available on request), where we found, apart from bipyramids, T_l for 2 <= l <= 10, and S5, S6, S7, six more graphs satisfying 1 not-in A, namely S_i with i = 2, 3, 4, 8, 9, 10.' This sentence is the only place where the 'only if' direction of Theorem 1.3 is completed for small triangulations. The six graphs enter Table 1 only through this unverifiable assertion; the code is not shipped (Appendix A contains code only for Propositions 6.1 and 6.2). The paper's central trichotomy for arbitrary finite A therefore depends on an external, non-certified computation. If the enumeration is incomplete, or if the type assigned to any of S2, S3, S4, S8, S9, S10 is wrong, Theorem 1.3 fails, and Corollary 4.7, Proposition 5.2, and the completeness of Table 2 all inherit the error. This concern is specific and structural: the rest of Section 2 is a hand proof, and the arithmetic checks, but this one step is neither derived nor shipped.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper classifies polyhedra (planar 3-connected graphs) by their type A(G), the set of all numbers |N(u,v)| of common neighbours over pairs of distinct vertices. Theorem 1.3 characterizes all polyhedra with 1 not in A: they are exactly the family S1 (bipyramids, T_l = P_l + K2, and ten exceptional graphs), with the type list of Table 1. Theorem 1.4 covers every polyhedron with 1 in A through Table 2: for the types {1,2}, {1,2,3} and {1,2,4}, everything outside a finite order bound (p <= 24, 47, 78) lies in a named infinite family (pyramids, W3, W4); the type {1,2,l} with l even >= 6 is exactly B_l or B'_l; the type {0,1} is exactly the class of polyhedra with no 4-cycles; {0,1,2} is characterized for order at least 25; and three construction propositions in Section 6 yield infinitely many polyhedra for the types {1,2,3} union A'_4, {1,2,4} union A'_5, and {0,1,2} union A'_3. Section 5 proves that no other types occur, giving the abstract's trichotomy: for every finite set A, the authors classify all polyhedra of that type, or construct infinitely many, or prove that none exist. The strategy combines a diameter-two domination bound (Lemma 3.5, via Goddard and Henning), a classification of radius-one polyhedra (Lemmas 4.1-4.3 and Propositions 4.4-4.5), a structural theorem for the type {1,2,l} (Proposition 5.1), and a small computer enumeration in Section 2 for triangulations of maximum degree at most 5.","tokens_in":18518,"tokens_out":50466,"duration_ms":529179,"significance":"If correct, the trichotomy is a complete, sharp classification of all planar 3-connected graphs by their common-neighbour spectrum, substantially extending the author's earlier classification of planar Deza graphs [8]; the statement is falsifiable, since a single polyhedron whose type is absent from Tables 1 and 2 would refute it. The analytic core is genuinely parameter-free: I re-derived the degree-bound reduction p <= 12 in Section 2 for Delta <= 5, the bound p <= 4M^2 + 3M + 2 in Lemma 3.5 from the Goddard-Henning domination input, the 24/47/78 arithmetic in Corollary 4.6, and the case split of Proposition 5.2, and found them consistent. The constructions in Section 6 are explicit, and Propositions 6.1 and 6.2 ship executable Mathematica verification code, a genuine reproducibility asset. Two caveats are load-bearing: the completeness of Theorem 1.3 (and the contrapositive step G not in S1 implies 1 in A that feeds Proposition 4.4 and hence most of Table 2) rests on an unshipped computer enumeration, and the proof of Lemma 3.6 contains an invalid counting step, although the lemma's statement is true.","major_comments":[{"comment":"Section 2, paragraph following the equation 12 = 3p3 + 2p4 + p5 >= p: the only-if direction of Theorem 1.3 for triangulations of maximum degree at most 5 is completed solely by the sentence stating that all triangulations with up to 12 vertices were inspected, with code available on request. This step is load-bearing: a missed triangulation (for instance one with type {0,2} or {2,4} on at most 12 vertices) would falsify Table 1, and the contrapositive that G not in S1 implies 1 in A is used in Proposition 4.4, hence in Proposition 4.5 and Corollaries 4.6 and 4.7, and therefore in Table 2's rows {1,2}, {1,2,3}, {1,2,4}, and {0,1,2}. The code is not shipped: Appendix A provides Mathematica code only for Propositions 6.1 and 6.2, so this step is neither derived nor certified in the manuscript. Since there are only about 9,000 unlabeled triangulations of the sphere with up to 12 vertices, the authors should ship the generating and checking code together with a certificate (for instance the complete list of such triangulations and their type sets), or replace the enumeration with a hand-checkable argument.","section":"Section 2 (enumeration of triangulations with up to 12 vertices)"},{"comment":"Section 3, Lemma 3.6, Eqs. (3.1) and the preceding paragraph: the deduction that f3 = f/2 does not follow from the statement that, for each vertex, exactly half of the faces containing it are triangular. Summing that statement over all vertices gives 3f3 = sum_{i>=5} i f_i (there are no 4-cycles, since A = {1} contradicts Corollary 3.3), which implies only f3 >= 5f/8; the displayed chain 2q >= 3f/2 + 5 sum_{i>=5} f_i = 3f/2 + 5(f - f3) = 3f/2 + 5f/2 = 4f uses f3 = f/2 in the last equality, so the contradiction 4p + 4r - 8 = 4q >= 4p + 4r is not obtained as written. The preceding pairing argument (u, v1, v2, then u, v3, v4, and so forth) also assumes without proof that the perfect matching induced by unique common neighbours pairs consecutive vertices in the cyclic order around u. The lemma's statement is nevertheless true: with A = {1}, every pair of vertices has exactly one common neighbour, and the Friendship Theorem forces a windmill graph, which is not 3-connected when it has at least two triangles (and K3 is not a polyhedron), so Corollary 3.7 and Proposition 5.2 stand once the proof is repaired. The proof as printed needs that repair.","section":"Section 3, Lemma 3.6 and Eq. (3.1)"}],"minor_comments":[{"comment":"The proof of Lemma 3.5 excludes the unique graph of Figure 9 from the Goddard-Henning domination statement [4, Theorem 2], but does not verify the claimed bound p <= 4M^2 + 3M + 2 for that exceptional graph. Since the applications in Corollary 4.6 require only the bounds 24, 47, and 78, an explicit check of that single graph, or a sentence explaining that its order lies below these bounds, would close the gap.","section":"Section 3, Lemma 3.5"},{"comment":"In the first case of Proposition 5.2, the proof that 2 not in A implies A = {0,1} rules out A = {1} via Lemma 3.6, but does not rule out A = {0} or A = empty; these are impossible for a connected graph of order at least 4 with diameter at least 2, and one sentence would suffice.","section":"Section 5, Proposition 5.2"},{"comment":"The symbol S1 is overloaded: it denotes both the family S1 := {bipyramids} union {T_l} union {S_i} and the exceptional graph S1 (the cube) in Figure 2 and Table 1; this should be disambiguated to avoid confusion in the statements of Theorem 1.3 and Proposition 4.4.","section":"Section 1, definition of S1"},{"comment":"The phrase 'Theorems 1.3 and Theorems 1.4' in Section 1 should read 'Theorems 1.3 and 1.4', and the opening sentence of Section 6, 'To complete the proof of Theorem 1.3', should refer to Theorem 1.4, since Theorem 1.3 is proved in Section 2.","section":"Sections 1 and 6, typography"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the manuscript is built largely on the author's own prior work (references [8], [9], and [10] are self-citations, and [8], the classification of planar Deza graphs, is itself an arXiv preprint), so the incremental novelty over [8] deserves editorial scrutiny. The load-bearing computation in Section 2 is asserted rather than shipped; given that reproducibility standards for a classification theorem may require code or a certificate, I recommend making the availability of the enumeration code and its output a condition of acceptance. Both technical problems I found (the Section 2 enumeration and the Lemma 3.6 proof step) are repairable within the scope of a revision, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is a genuine classification result, not a sketch. The trichotomy for all finite sets A is new, and the proofs are mostly hand-checkable. The one real soft spot is the unshipped computer enumeration behind Theorem 1.3; everything else I checked holds up.\n\nWhat's new: Theorem 1.3 and 1.4 together give a complete trichotomy for every finite set of non-negative integers: classify, construct infinitely many, or prove none. That's a clean statement, and it genuinely extends the author's earlier planar Deza graph classification from regular graphs to all 3-connected planar graphs. The families B_ell, B'_ell, W3, W4 are new, and the iff characterizations (e.g., A={1,2,ell} for even ell) are the sort of thing that makes the paper useful. The proofs are parameter-free, and I found no circularity. I checked the algebraic skeleton: Lemma 3.5's bound p <= 4M^2+3M+2, the arithmetic leading to p <= 24/47/78, the case split in Proposition 5.2, and boundary cases like the square pyramid. All consistent.\n\nSoft spots: the stress-test note is right. Section 2 completes the 'only if' of Theorem 1.3 for triangulations with delta <= 5 via a computer inspection of all triangulations up to 12 vertices, with code 'available on request'. That's a load-bearing finite check, and the paper doesn't ship the code or a certificate. If the enumeration missed a graph, the classification collapses. This is fixable, and it's small enough for an independent check, but it needs to be resolved before the paper is trusted. A second, minor issue: the abstract says 'classify all polyhedra of that type,' but for {1,2}, {1,2,3}, {1,2,4} the result only bounds the order (24,47,78) outside the named families; the finite exceptions are not listed. That's a framing mismatch, not a mathematical error. Finally, a few planarity arguments are asserted with 'by planarity this cannot happen' rather than expanded; they look right from the figures, but they are not machine-checked.\n\nWho it's for: people working on planar graph structure, Deza graphs, or common-neighbour invariants. It deserves a serious referee. I would ask the author to provide the enumeration code or a verification script, and to adjust the abstract's wording. After that, accept.","headline":"A credible and substantial classification of polyhedral graphs by common-neighbour sets, with one unshipped finite enumeration worth verifying before acceptance.","tokens_in":19380,"tokens_out":2648,"would_cite":true,"duration_ms":29732,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C75","05C69","05C12","05E30","52B05","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a complete three-way classification of polyhedra by their sets of common-neighbour counts.","keywords":["planar graph","polyhedron","common neighbours","3-polytope","Deza graphs","strongly regular graphs","graph radius","graph classification"],"falsifier":"Re-run the enumeration of Section 2 with an independent, certified program that lists all 3-connected planar triangulations on at most 12 vertices and checks whether $1\\notin A(G)$; finding any such graph beyond the six named $S_2,S_3,S_4,S_8,S_9,S_{10}$ (and beyond bipyramids and $T_\\ell$) would disprove Theorem 1.3.","tokens_in":18014,"feed_emoji":"🔷","tokens_out":11237,"duration_ms":117423,"temperature":0.7,"pith_summary":"This paper proposes a complete classification of polyhedra—planar, 3-connected graphs—by their type, defined as the set of numbers of common neighbours that occur among pairs of distinct vertices. For every finite set $A$ of non-negative integers, the author claims exactly one of three outcomes: all polyhedra of type $A$ are explicitly classified, infinitely many are constructed, or none exist. The proof splits at whether $1\\in A$: when $1\\notin A$ every polyhedron lies in the short family $S_1$ (bipyramids, the graphs $T_\\ell$, and ten exceptional graphs, Table 1), and when $1\\in A$ the type must appear in Table 2, where the remaining infinite families are pyramids, $W_3$, $W_4$, $B_\\ell/B'_\\ell$, or the explicitly constructed unions with $A'_n$. This gives a complete answer to a question that generalizes the earlier classification of regular polyhedra by common-neighbour types.","feed_headline":"Common-neighbour counts classify every polyhedron","feed_subtitle":"For any finite set of numbers, polyhedra with those counts are listed, infinite, or impossible.","key_machinery":"The argument is carried by the type set $A(G)=\\{|N(u,v)| : u,v\\in V(G), u\\ne v\\}$ together with three structural tools. First, the reduction lemmas show that in a planar graph $2\\in A$ whenever some $a\\ge3$ lies in $A$, and $2\\in A$ is equivalent to containing a 4-cycle, so the absence of $2$ forces $A\\subseteq\\{0,1\\}$. Second, for radius-1 polyhedra the plane neighbourhood $\\Gamma_u(G)$ of a dominating vertex is a pyramid, so the graph is a pyramid plus added edges; this yields the characterizations of $W_3$ and $W_4$. Third, for radius at least 2 and $0\\notin A$, a bound $p\\le4M^2+3M+2$ on the order follows from domination in planar graphs of diameter 2, which is what turns the types $\\{1,2\\},\\{1,2,3\\},\\{1,2,4\\}$ into finite searches plus explicit families.","core_discovery":"The central discovery is that the common-neighbour spectrum $A(G)$ is a classifying invariant for polyhedra: the paper proves a trichotomy for every finite set $A$ of non-negative integers. If $1\\notin A$, Theorem 1.3 states that $G\\in S_1$ exactly, with the full type decomposition in Table 1—tetrahedron, cube, icosahedron, octahedron, the graphs $T_3, T_4, T_\\ell$, the ten exceptions $S_1,\\dots,S_{10}$, and the bipyramids. If $1\\in A$, Theorem 1.4 asserts that $A(G)$ is one of the listed types, and for each listed type the corresponding polyhedra are either characterized (e.g. $A=\\{0,1\\}$ exactly when no 4-cycles are present), bounded in order by $24,47,78$ outside the named families, equal to $B_\\ell$ or $B'_\\ell$ for even $\\ell\\ge6$, or proven to occur infinitely often via explicit constructions. Together these two theorems exhaust all possible types.","pith_inferences":["The trichotomy is special to planarity: Lemma 3.1 does not hold for general graphs, since complete graphs satisfy $A(K_n)=\\{n-2\\}$, so the same three-outcome classification cannot be expected for all graphs.","The order bounds $24,47,78$ come from a generic domination bound for planar diameter-2 graphs; a sharper bound of that kind would shrink the finite checks and could make the classification effectively verifiable by enumeration.","The caterpillar and gluing constructions of Section 6 provide infinite families with prescribed common-neighbour sets; these families could serve as explicit generators for testing network algorithms that use common-neighbour similarity."],"forward_implications":["For every finite set $A$ of non-negative integers, exactly one of the trichotomy outcomes holds: all polyhedra of type $A$ are classified, infinitely many exist, or none exist.","A polyhedron has $A=\\{0,1\\}$ if and only if it contains no 4-cycles, hence every polyhedron of girth at least 5 has type $\\{0,1\\}$.","All polyhedra of type $\\{1,2\\}$, $\\{1,2,3\\}$, or $\\{1,2,4\\}$ are, outside orders $p\\le24$, $p\\le47$, and $p\\le78$ respectively, exactly the $n$-gonal pyramids, the class $W_3$, and the class $W_4$.","For even $\\ell\\ge6$, the only polyhedra with $1\\in A$, $0,3,4\\notin A$, and $\\ell\\in A$ are $B_\\ell$ and $B'_\\ell$.","A polyhedron on at least 25 vertices has $A=\\{0,1,2\\}$ if and only if it is not a pyramid, contains a 4-cycle, and contains no subgraph isomorphic to $K(2,3)$."],"supporting_citations":[{"why":"classifies the regular case by type and already supplies the wide classes for types {0,1} and {0,1,2} that the present paper extends to all polyhedra.","marker":"[8]"},{"why":"supplies the domination bound for planar graphs of diameter 2 used in Lemma 3.5 to bound the order when radius is not 1.","marker":"[4]"},{"why":"provides the Hamiltonian/outerplanar lemma that makes the plane neighbourhood of a radius-1 vertex a pyramid.","marker":"[9]"},{"why":"gives the caterpillar degree-sequence formula and the pyramid-plus-edges construction used to build infinite families in Propositions 6.1 and 6.2.","marker":"[10]"},{"why":"establishes uniqueness of planar embeddings for 3-connected graphs, allowing the paper to work with a fixed planar embedding of each polyhedron.","marker":"[16]"}],"fun_headline_variants":["Polyhedron types: finite, infinite, or none","Common-neighbour spectrum sorts all polyhedra","A trichotomy for polyhedron classification","Every polyhedron categorized by neighbour counts","Finite sets of neighbour counts classify polyhedra"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The completeness of Table 1 rests on a computer enumeration of all triangulations with up to 12 vertices, reported in Section 2; if that enumeration missed any triangulation with $1\\notin A$, the classification would be incomplete and later statements relying on Table 1 would inherit the gap.","fun_headline_variants_meta":{"raw":{"variants":["Polyhedron types: finite, infinite, or none","Common-neighbour spectrum sorts all polyhedra","A trichotomy for polyhedron classification","Every polyhedron categorized by neighbour counts","Finite sets of neighbour counts classify polyhedra"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000173,"raw_usage":{"total_tokens":1235,"prompt_tokens":859,"completion_tokens":376,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":307}},"tokens_in":475,"tokens_out":376,"duration_ms":4681,"temperature":1.0,"reasoning_tokens":307,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T05:46:53.767935+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the enumeration of Section 2 with an independent, certified program that lists all 3-connected planar triangulations on at most 12 vertices and checks whether $1\\notin A(G)$; finding any such graph beyond the six named $S_2,S_3,S_4,S_8,S_9,S_{10}$ (and beyond bipyramids and $T_\\ell$) would disprove Theorem 1.3.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"classifies the regular case by type and already supplies the wide classes for types {0,1} and {0,1,2} that the present paper extends to all polyhedra."},{"cited_title":"Goddard and M","cited_arxiv_id":null,"evidence_quote":"supplies the domination bound for planar graphs of diameter 2 used in Lemma 3.5 to bound the order when radius is not 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the caterpillar degree-sequence formula and the pyramid-plus-edges construction used to build infinite families in Propositions 6.1 and 6.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes uniqueness of planar embeddings for 3-connected graphs, allowing the paper to work with a fixed planar embedding of each polyhedron."}],"review_version":1}