{"id":"c4303e7a-516d-40ce-b1f6-7a3ac60879c5","arxiv_id":"2411.13473","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Polyhedral (planar, 3-connected) graphs are Kronecker products in at most one way, and the polyhedra expressible as Cartesian or Kronecker products in multiple ways are classified.","lead":"A graph multiplication called the Kronecker product can sometimes be undone in two different ways, but this paper shows that for polyhedral graphs the factorization is unique. It also finds all polyhedra that have more than one graph-product representation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.10's proof has an unjustified exhaustiveness step: non-isomorphism is asserted to force the factor regions R and S to cross, and planarity is then used to infer adjacency of arbitrary vertices on the crossing cycle.","rationale":"The reader correctly identifies the black-box use of [15, Theorem 1.3] as a dependency, but the single most load-bearing concern is the unverified exhaustiveness of the overlay proof in Theorem 1.10. That proof is the entire argument for the paper's main claim: cancellation for planar 3-connected Kronecker products. The step from 'two factorizations of the same product' to 'J is isomorphic to L' depends on several asserted facts about how the distinguished regions R and S interact: that non-isomorphism forces nontrivial crossing, that each copy of S crosses between the two copies of J', and that certain vertices on the same cycle must be adjacent by planarity. None of these facts is proved, and each is essential. If any configuration is missed, the conclusion J ≃ L does not follow. This concern does not amount to a known counterexample, so the appropriate disposition remains the reader's CONDITIONAL verdict rather than rejection: the theorem is plausible and the paper is a solid contribution, but the main proof needs to be made rigorous or independently checked. The proposed computational search is a concrete way to test the claim directly, and a formalization of the overlay argument would settle the exhaustiveness question.","tokens_in":21265,"tokens_out":4827,"duration_ms":59924,"concrete_test":"Run an exhaustive computational search over all non-isomorphic simple graphs J with up to 8 vertices (using nauty/geng): compute P = J ∧ K2, test planarity and 3-connectivity, and group the resulting products by isomorphism class. If any product class is realized by two non-isomorphic graphs J and L, Theorem 1.10 is false; if no such pair exists through this range, the informal overlay proof receives independent support. A second, more targeted check would be to test, on the same data, whether any pair of non-isomorphic factors produces a product in which the distinguished cycles R and S coincide, since the proof's first dichotomy assumes this cannot happen.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing defect is inside the proof of Theorem 1.10, not in the cited classification. After overlaying the two factorizations, the proof asserts that if J is not isomorphic to L, then 'S does not coincide with R' and that each copy of S contains a positive even number of the J-cross edges (4.1). Neither assertion is derived. R and S are two cycles in the same planar embedding; they could coincide, be disjoint, or be nested even when the factors are non-isomorphic, and the proof gives no argument excluding these configurations. The subsequent step 'by planarity these two vertices are in fact adjacent' is also not a consequence of two vertices lying on the same cycle. Thus the argument appears to verify the drawn configurations of Figures 14-15 rather than the general case. The dependence on [15, Theorem 1.3] is a real external assumption, but it is not the immediate bottleneck: even assuming the classification is complete, the overlay proof needs a rigorous case analysis showing that the constructed isomorphism J ≃ L covers all possible relative placements of R and S. As written, the main theorem is supported by an informal planar-intuition argument, which is exactly the part of the paper that most needs tightening.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Kronecker (direct) products A ∧ B that are planar and 3-connected (polyhedral). Its main result is Theorem 1.10: if J ∧ K2 ≃ L ∧ K2 is a 3-polytope, then J ≃ L, i.e., cancellation holds for Kronecker products when the product is a polyhedron. The authors also classify face-regular and vertex-regular polyhedral Kronecker products (Theorems 1.4–1.8), characterize planar graphs that are Cartesian products in two distinct ways, and identify the polyhedra that are both Kronecker and Cartesian products (Theorem 1.11, Corollary 1.12). The proofs rely heavily on the prior classification of polyhedral Kronecker products by the second author [15].","tokens_in":21467,"tokens_out":9798,"duration_ms":97311,"significance":"If correct, the main theorem is a substantial contribution to the open problem of Kronecker cancellation for simple graphs: it establishes the first natural class of products for which cancellation always holds, complementing known counterexamples such as the Petersen graph. The regularity classifications are also valuable: they give concrete, constructive characterizations (Theorems 1.4, 1.6, 1.8) with explicit transformations and examples, and Theorem 1.11 completes the picture of simultaneous Cartesian and Kronecker representations. The paper is well written and the auxiliary results are mostly convincing. However, the proof of the central theorem, Theorem 1.10, contains a load-bearing gap: its key steps are justified only by planar-intuition arguments and figures rather than by a rigorous case analysis. The claimed result is plausible, but the proof as written does not establish it in full generality.","major_comments":[{"comment":"The assertion that if J is not isomorphic to L then 'S does not coincide with R' and that each copy of S contains a positive even number of edges from (4.1) is not proved. R and S are cycles in the same planar embedding, and non-isomorphism of the factors does not by itself exclude configurations where S and R are disjoint, equal, or nested. The subsequent case analysis therefore does not cover all possible relative placements of R and S, and the argument appears to verify only the configurations drawn in Figures 14 and 15.","section":"§4.1, proof of Theorem 1.10 (paragraph after Eq. (4.2))"},{"comment":"The statement 'by planarity these two vertices are in fact adjacent' is not a valid consequence of the fact that two vertices lie on the same cycle S. Two vertices on a cycle need not be adjacent, and planarity alone does not imply adjacency. The proof seems to assume without justification that the overlay of R and S forces the specific local pattern of consecutive vertices used in the construction of the 4-cycles and the eventual isomorphism J ≃ L. A rigorous argument is needed to show that all configurations reduce to this pattern.","section":"§4.1, proof of Theorem 1.10 (paragraph 'Since (dα, y) and (dβ, x) ...')"},{"comment":"The construction of the isomorphism J ≃ L via the graphs G1 and G2 is described verbally and with reference to Figures 14 and 15, but G1 and G2 are not defined formally, and the proof does not verify that the proposed correspondence is a graph isomorphism in all cases, especially when a copy of S contains several edges from (4.1). The sentence 'Please note that the above reasoning holds for any number of pairs of edges from (4.1) that a copy of S may contain' is an assertion of generality that is not accompanied by a proof.","section":"§4.1, end of proof of Theorem 1.10"}],"minor_comments":[{"comment":"The exclusion of the first ordering of vertices on R ('otherwise a1x, b1x, a1y, b1y would all lie on the same face in P') is not fully justified; a short explanation or small figure would clarify why this forces a non-quadrangular face.","section":"§2.1, proof of Theorem 1.4"},{"comment":"In the statement of Theorem 1.11, the two families 'C4n+2 □ Pm, n ≥ 1, m ≥ 2' and 'C4n □ P2m, n, m ≥ 1' are written as separate cases; it may be worth stating explicitly that the cube itself is excluded from the 'expressible in two ways' part, as is done in the text.","section":"§1.4, Theorem 1.11"},{"comment":"The sentence 'Since the only cycle graph containing a copy of C4 is C4 itself, n must be 4' is slightly imprecise: a cycle graph C_n contains C4 as a subgraph only when n = 4; the intended meaning is clear, but the wording could be tightened.","section":"§4.2, proof of Proposition 4.1"},{"comment":"The paper cites the classification from [15] as a black box (Theorem 1.3). Since the main theorem depends on this classification, the authors should state explicitly that Theorem 1.10 is contingent on the full correctness of [15], and ideally indicate whether [15] has been peer-reviewed.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The proof of Theorem 1.10 is the centerpiece of the paper, and it is currently not rigorous enough for publication. The gap is not a matter of style: the argument assumes a specific overlay configuration without proving exhaustiveness. I would advise the editor that a major revision is needed, with a complete formal case analysis for the proof of Theorem 1.10. Additionally, the paper's reliance on [15] (an arXiv preprint by the same author) should be verified; if [15] is not yet accepted, the editor may want to request that the authors either include the necessary parts of the classification or confirm its status."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper has a genuinely new and interesting main result — polyhedral graphs are Kronecker products in at most one way — but the proof of that result is not yet rigorous. It reads like a detailed picture proof with a few assertions that need a proper case analysis.\n\nWhat is new and good: Theorem 1.10 proves cancellation for polyhedral Kronecker products, a natural special case of a known open problem. Theorems 1.4–1.8 give structural characterizations of face-regular and vertex-regular products, with constructive proofs and illustrations that look plausible. Theorem 1.11 completes the classification of simultaneous Cartesian/Kronecker products, which is a useful reference result. The paper builds transparently on the second author's earlier classification [15] and does not hide that dependence.\n\nThe soft spot is Theorem 1.10. After overlaying the two factorizations, the proof asserts that if J is not isomorphic to L then S does not coincide with R and the boundaries must cross. That is not derived. R and S are cycles in the same planar embedding; they could coincide, be nested, or be disjoint even when the factors are non-isomorphic, and the text does not rule those out. Later, \"by planarity these two vertices are in fact adjacent\" is not a consequence of lying on the same cycle. The step where the orders are set \"w.l.o.g.\" is doing a lot of work. As written, the argument verifies the drawn configurations in Figures 14 and 15 rather than the general case. The dependence on [15, Theorem 1.3] as a black box is a separate concern, but it is not the main bottleneck; even assuming that classification, the overlay step needs a rigorous case analysis.\n\nThe rest of the proofs are sketchier than I would like in places (for example, in Theorem 1.6, phrases like \"we cannot introduce any other vertices without violating\" carry the argument), but those parts are less load-bearing and likely fixable with more detail.\n\nWho this is for: people working on graph products, especially cancellation phenomena and product uniqueness. The main theorem is a natural milestone, and the simultaneous product classification is a useful reference.\n\nRecommendation: send to referees. The result is likely correct and important enough to warrant referee time, but the referee should demand a formal proof of Theorem 1.10 — specifically a clean case analysis of the relative placements of R and S. With that tightened, this would be a strong paper.","headline":"Polyhedral Kronecker cancellation is a real result, but the main proof is an informal picture argument that needs a rigorous case analysis before it is publishable.","tokens_in":22054,"tokens_out":3581,"would_cite":true,"duration_ms":39419,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C76","05C35","05C10","05C75","05C85","52B05","52B10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A 3-connected planar graph has at most one Kronecker factorization","keywords":["Kronecker product","cancellation","polyhedral graph","Kronecker cover","quadrangulation","cubic graph","Cartesian product","3-connected planar graph"],"falsifier":"Enumerate all simple graphs $J$ on up to a fixed number of vertices whose Kronecker cover $J\\wedge K_2$ is a given small polyhedron, such as the cube or the stacked cube $C_4\\square P_4$, checking isomorphism of the covers directly from the product definition. The theorem predicts exactly one such $J$ for each polyhedral cover; any second non-isomorphic preimage would refute Theorem 1.10.","tokens_in":21022,"feed_emoji":"🧩","tokens_out":9270,"duration_ms":86862,"temperature":0.7,"pith_summary":"This paper asks how uniquely a highly structured class of planar graphs can be decomposed into graph products. The main result is that cancellation holds for the Kronecker product when the product is planar and 3-connected: if $J\\wedge K_2 \\simeq L\\wedge K_2$ and this product is a 3-polytope, then $J\\simeq L$. Equivalently, the graph of a polyhedron is a Kronecker product in at most one way. This is a positive special case of a general cancellation question for Kronecker products, which is known to fail in other settings. The paper also classifies face-regular and vertex-regular polyhedral Kronecker products and characterises the planar graphs that are Cartesian products in two ways or both Kronecker and Cartesian products.","feed_headline":"Polyhedral graphs are Kronecker products in only one way","feed_subtitle":"A planar 3-connected graph can't have two different Kronecker factorizations—cancellation holds where it usually fails.","key_machinery":"The central object is the Kronecker (direct) product of graphs, in the special form $J\\wedge K_2$, called the Kronecker cover or double cover of $J$. The load-bearing machinery is the structural description of polyhedral Kronecker products: whenever $J\\wedge K_2$ is a 3-polytope, $J$ is built from a planar bipartite core $J'$ plus a matching $a_1b_1,\\dots,a_mb_m$ whose endpoints all lie on one region $R$ in one of two cyclic orders. The cancellation proof overlays two such factorizations on the same sphere, and the uniqueness of the embedding of a 3-connected planar graph forces the two copies of the region $R$ and the matching edges to align, so that the two factor graphs agree.","core_discovery":"The central claim is that a polyhedral graph has at most one representation as a Kronecker product. Since a 3-polytopal Kronecker product must have $K_2$ as one factor, the statement is precisely: $J\\wedge K_2 \\simeq L\\wedge K_2$ with the common product a 3-polytope implies $J\\simeq L$. The proof takes two factorizations of the same polyhedron, overlays them on the same planar embedding, and uses the uniqueness of planar embeddings of 3-connected graphs together with the forced facial 4-cycles to identify the two factor graphs. Alongside this, the paper establishes that the face-regular polyhedral Kronecker products are exactly the 3-connected quadrangulations of the sphere, the vertex-regular ones are exactly the cubic polyhedra, and it describes the extremal class with the fewest vertices of degree 3. It also determines which polyhedra have two distinct Cartesian decompositions and which are simultaneously Kronecker and Cartesian products.","pith_inferences":["The overlay argument used in the cancellation proof may extend to other graph classes with unique embeddings, such as 3-connected graphs on higher-genus surfaces, where a surface-specific uniqueness theorem would replace Whitney's planar result.","The iterative constructions in Theorems 1.6 and 1.8 give an explicit supply of extremal polyhedra; these families could be used to computationally test the open problem of polyhedral Kronecker products with exactly six quadrangular faces.","Because the known counterexample to cancellation (the Desargues graph as a common cover of two non-isomorphic graphs) fails planarity, the boundary drawn by Theorem 1.10 suggests that planarity together with 3-connectivity, rather than bipartiteness alone, is the right rigidity condition for Kronecker uniqueness."],"forward_implications":["A polyhedral graph has a unique Kronecker decomposition, so any algorithm searching for Kronecker factorizations of polyhedra can stop once the factor $J$ is found.","The Kronecker cancellation problem for simple graphs has a positive answer whenever the common cover is planar and 3-connected, even though it is false in general.","The face-regular polyhedral Kronecker products are exactly the 3-connected quadrangulations of the sphere described in Theorem 1.4, and the vertex-regular ones are exactly the cubic polyhedra described in Theorem 1.8.","A planar graph is a Cartesian product in at most two ways, with the stacked cubes other than the cube as the only ambiguous cases; the polyhedra that are both Kronecker and Cartesian products are precisely the two families listed in Theorem 1.11.","Among stacked cubes, $C_4\\square P_{2m}$ for $m\\ge 2$ has a unique Kronecker factorization whose factor $J$ is non-planar, while its two Cartesian factorizations are also distinct."],"supporting_citations":[{"why":"Supplies the classification and construction of all 3-polytopal Kronecker products, which the main theorem and all regularity results take as their starting point.","marker":"[15]"},{"why":"Provides the background theory of graph products, the general cancellation results, and the reduction of Kronecker cancellation to the question of uniquely recovering $J$ from $J\\wedge K_2$.","marker":"[9]"},{"why":"Gives the classical counterexample where cancellation fails, the Desargues graph being the common Kronecker cover of two non-isomorphic graphs, which motivates the special case studied here.","marker":"[12]"},{"why":"Shows that among generalized Petersen graphs the Desargues graph is the only one with multiple Kronecker covers, giving a near-miss family that brackets the polyhedral uniqueness result.","marker":"[13]"},{"why":"Provides Whitney's theorem that 3-connected planar graphs have a unique planar embedding, used in the proof of the main cancellation theorem.","marker":"[21]"},{"why":"The Steinitz-Rademacher theorem identifying planar 3-connected graphs with 1-skeletons of polyhedra, which is the class throughout the paper.","marker":"[19]"}],"fun_headline_variants":["Polyhedral Kronecker products cancel uniquely","Unique Kronecker factorization for polyhedral graphs","Cancellation holds for polyhedral Kronecker products","One Kronecker way for 3-connected planar graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the main theorem inherits, without re-deriving, the full classification of polyhedral Kronecker products from the companion paper: every such product is $J\\wedge K_2$ with $J$ of the special shape described in Definition 1.2, and if that classification missed a case, the cancellation argument would not cover it.","fun_headline_variants_meta":{"raw":{"variants":["Polyhedral Kronecker products cancel uniquely","Unique Kronecker factorization for polyhedral graphs","Cancellation holds for polyhedral Kronecker products","One Kronecker way for 3-connected planar graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1535,"prompt_tokens":1028,"completion_tokens":507,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":644,"completion_tokens_details":{"reasoning_tokens":446}},"tokens_in":644,"tokens_out":507,"duration_ms":5427,"temperature":1.0,"reasoning_tokens":446,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:22:12.489060+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all simple graphs $J$ on up to a fixed number of vertices whose Kronecker cover $J\\wedge K_2$ is a given small polyhedron, such as the cube or the stacked cube $C_4\\square P_4$, checking isomorphism of the covers directly from the product definition. The theorem predicts exactly one such $J$ for each polyhedral cover; any second non-isomorphic preimage would refute Theorem 1.10.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the background theory of graph products, the general cancellation results, and the reduction of Kronecker cancellation to the question of uniquely recovering $J$ from $J\\wedge K_2$."},{"cited_title":"Imrich and T","cited_arxiv_id":null,"evidence_quote":"Gives the classical counterexample where cancellation fails, the Desargues graph being the common Kronecker cover of two non-isomorphic graphs, which motivates the special case studied here."},{"cited_title":"Krnc and T","cited_arxiv_id":null,"evidence_quote":"Shows that among generalized Petersen graphs the Desargues graph is the only one with multiple Kronecker covers, giving a near-miss family that brackets the polyhedral uniqueness result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Whitney's theorem that 3-connected planar graphs have a unique planar embedding, used in the proof of the main cancellation theorem."},{"cited_title":"Steinitz and H","cited_arxiv_id":null,"evidence_quote":"The Steinitz-Rademacher theorem identifying planar 3-connected graphs with 1-skeletons of polyhedra, which is the class throughout the paper."}],"review_version":1}