{"id":"eebc9bb6-1b39-41c3-b2c7-7e82fb4779e1","arxiv_id":"2506.09264","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Cactus graphs satisfy the strong bunkbed conjecture, and any graph satisfies the conjecture if and only if all of its biconnected components do.","lead":"This paper proves that the bunkbed conjecture, a long-standing percolation inequality, still holds for cactus graphs and for graphs assembled from certain simple pieces. The main tool is a reduction showing the conjecture holds globally exactly when it holds on every biconnected component, which gives a classification scheme for graphs that survive the conjecture's recent refutation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's minor obstruction rests on an unproved classification lemma: the claim that every biconnected graph on at least five vertices that is not a cycle contains one of the two specified diamond subdivisions as a minor is only asserted, so the minor obstruction is not established.","rationale":"I read the main structural proof carefully. The block decomposition in Theorem 1b and Theorem 1 appears correct: the two cases in the 'if' direction decompose connection probabilities using independence and mirroring arguments, and the induction in Theorem 1 is valid. Proposition 7 and Theorem 2 are built on Lemmas A-C and are coherent. The weak-version Theorem 3 depends on external citations that I did not verify; I therefore did not make that the primary concern. The single most load-bearing gap is the classification in Theorem 4, exactly as the reader identified. The paper labels it 'easy to see' and repeats it in the sketch without proof. Since Theorem 4 and the final assertion of Theorem 13 are stated results in the abstract and body, the paper should not be accepted without this lemma being proven or independently verified. I agree with the reader's CONDITIONAL verdict and recommend no change to the verdict.","tokens_in":16142,"tokens_out":44765,"duration_ms":472497,"concrete_test":"Prove or disprove the classification lemma by a rigorous ear-decomposition argument: Let G be biconnected, |V(G)| >= 5, and not a cycle. Take a cycle C and repeatedly add ears. If any ear has length at least 2, C together with that ear contains a theta subgraph; contracting two of the three internally disjoint paths yields K_{2,3} as a minor. If all ears have length 1, then G is a cycle with chords. If some chord closes a cycle of length at least 5, contract along that cycle to obtain the house graph (C5 with a chord) as a minor; if all chorded cycles have length 4, the graph is built from diamonds and either has at most four vertices or, if larger, contains K_{2,3} or the house graph as a minor (for example, two diamonds sharing an edge contain the house graph as a subgraph).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4 (Section 2, final proof) is a single sentence: 'It is easy to see that any biconnected graph with more than four vertices that is not a cycle must contain one of the two graphs given in Theorem 4 as a minor.' The later sketch of the forbidden minors for G4 defers to the same statement in its '⊆' direction: 'Verify that every biconnected graph with at least five vertices that is not a cycle must contain one of the two graphs above as a minor.' Thus the full content of the minor obstruction is an unproved graph-theoretic classification: the graphs with no K_{2,3} minor and no house-graph minor should be exactly the cycles plus graphs on at most four vertices. If this classification is false, Theorem 4 fails, and the final sentence of Theorem 13 (every minimal counterexample contains a non-trivial subdivision of the diamond graph as a minor) loses its support. The lemma is not obviously true: K_{2,3} and the house graph are the two 5-vertex, 6-edge biconnected graphs, but excluding both as minors imposes a nontrivial structural restriction that needs a proof. The claim is plausible, and I do not know of a counterexample, but the paper does not supply the required argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the bunkbed conjecture for finite simple graphs, distinguishing the weak version (constant edge probability) from the strong version (individual edge weights). Its central result is a block decomposition theorem (Theorem 1): a graph satisfies the weak or strong bunkbed conjecture if and only if every biconnected component does. This is proved via a two-block gluing lemma (Theorem 1b) that is the probabilistic heart of the paper. The paper then proves the strong conjecture for all cactus graphs (Theorem 2) and, more generally, for graphs whose blocks are cycles or have at most four vertices (Theorem 11). Combining with earlier results by other authors, it proves the weak conjecture for graphs whose blocks belong to previously known classes (Theorem 3). Finally, it derives minor obstruction statements: every counterexample to the strong conjecture contains one of two five-vertex graphs as a minor (Theorem 4), and, assuming the class of strong-counterexamples is minor-closed, a finite set of forbidden minors exists (Theorem 13).","tokens_in":16378,"tokens_out":23032,"duration_ms":253035,"significance":"If correct, the block decomposition theorem is a valuable and natural reduction of the bunkbed conjecture to biconnected components, and Theorem 2 substantially enlarges the known class of graphs satisfying the strong version. The probabilistic arguments in Theorem 1b and Lemmas A-C are detailed, self-contained, and largely checkable, and the paper is generally clearly written. The main weaknesses are concentrated in the final minor-related results: the classification lemma behind Theorem 4 is only asserted as 'easy to see', and the minor-closedness argument behind Theorem 13 is only sketched. These gaps do not affect the validity of the cactus result or the weak-conjecture block extension, but they do affect the advertised minor obstruction theorems.","major_comments":[{"comment":"The proof of Theorem 4 consists of the sentence 'It is easy to see that any biconnected graph with more than four vertices that is not a cycle must contain one of the two graphs given in Theorem 4 as a minor.' This is a non-trivial structural classification and it is the whole content of the minor obstruction. The later paragraph after Theorem 4 ('As for a quick sketch...') does not supply a proof either: its '⊆' direction explicitly asks the reader to 'Verify' the same statement. Please give a complete argument, for example via ear decomposition, showing that a biconnected non-cycle contains a theta subgraph whose contraction yields either K_{2,3} or the house graph. Until this is supplied, Theorem 4, and the final assertion of Theorem 13 that every minimal counterexample contains a non-trivial subdivision of the diamond graph as a minor, are not established.","section":"Section 2, proof of Theorem 4"},{"comment":"The minor-closedness of the class of strong-bunkbed graphs is asserted in one sentence: 'assigning certain edges e∈E(G) an edge weight of p_e=0 or p_e=1 corresponds to deleting or contracting these edges.' This needs a careful verification. Deleting a vertex requires setting all incident horizontal probabilities to 0 and then showing the isolated vertex cannot contribute to any connection because its posts are disconnected from the rest; contracting an edge with p=1 requires checking that the choice of posts for the preimage of T in the contracted graph reproduces exactly the bunkbed inequality. Since the finite-forbidden-minor conclusion is obtained by applying the graph minor theorem to this class, the closure property is load-bearing and should be proved in detail.","section":"Section 2, proof of Theorem 13"}],"minor_comments":[{"comment":"The countable-graph remark is unsupported: the paper's proofs are for finite graphs, and the text itself notes that the proof of Theorem 1 would have to be adjusted. Either provide the adjusted proof or state explicitly that the countable extension is not proved here.","section":"Introduction, countable-graph remark"},{"comment":"The two graphs in Theorem 4 are given only by figures; please define them in words (they are the K_{2,3} graph and the house graph) so that the statement and the proof are self-contained.","section":"Theorem 4 statement"},{"comment":"In Lemma B, the quantity d is introduced with vertices u and v but is then used with v and w; please correct the notation.","section":"Section 2, Lemma B"},{"comment":"The phrase 'we may carefully cancel out terms' in Lemma B is too terse; the cancellation should be written out, since it is the algebraic core of the lemma.","section":"Section 2, Lemma B"},{"comment":"There are several typographical errors: 'seperately', 'atleast', 'adressed', and 'en' (in the proof of Theorem 1) should be corrected.","section":"Throughout"},{"comment":"In the proof of Proposition 8, the statement that every vertex of a biconnected non-trivial block has degree at least 2 is 'easy to see'; a one-sentence justification would avoid relying on the reader's tolerance.","section":"Section 2, Proposition 8"}],"recommendation":"major_revision","confidential_remarks":"The overlap with [MP24] is disclosed in a footnote, so there is no novelty concern on that point. The missing classification lemma is the only serious technical gap; I would not reject the paper if the author supplies a proof. The paper is within the scope of the journal and the main block-decomposition and cactus results appear sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main contribution is Theorem 1: the bunkbed conjecture (weak or strong) holds for a graph iff it holds for every biconnected component. This is a clean reduction, and the proof via the gluing lemma (Theorem 1b) is detailed and the probability decompositions check out. The cactus-graph result (Theorem 2) follows naturally and gives a broad new class for the strong version. The paper is well-structured and honestly discloses the overlap with [MP24].\n\nThe soft spot is real. Theorem 4, which is used to conclude that every counterexample contains a diamond subdivision as a minor, relies on the claim that every biconnected graph with at least five vertices that is not a cycle contains one of two specified diamonds as a minor. That claim is asserted as \"easy to see\" in the proof and later deferred again in the sketch. The stress-test note is right: this is a nontrivial structural classification and the paper does not supply the argument. The claim is plausible, and I don't know a counterexample, but it is not established.\n\nTheorem 13 also depends on this classification in its final sentence, and its minor-closedness argument is terse. The idea that setting edge weights to 0 or 1 corresponds to deletion or contraction is reasonable, but it deserves a more careful statement (especially regarding posts). These are fixable issues, not signs of a broken core.\n\nOverall: this is a serious contribution to the post-counterexample classification program. The block theorem and cactus proof are valuable on their own. The missing graph-theoretic lemma is a genuine gap that should be patched before publication, but it does not undermine the rest of the paper if the lemma is true.\n\nI'd send this to a serious referee. The referee should be asked to verify the classification lemma in Theorem 4 and to tighten the minor-closedness argument in Theorem 13. With those fixed, the paper would be accept-worthy.","headline":"Solid block-decomposition and cactus-graph results; the minor obstruction in Theorem 4 rests on an unproved 'easy to see' classification that needs a real argument.","tokens_in":16937,"tokens_out":910,"would_cite":true,"duration_ms":12720,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K35","05C80","05C40","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the bunkbed conjecture reduces to biconnected components, that every cactus graph satisfies the strong version, and that any counterexample must contain a subdivision of the diamond graph as a minor.","keywords":["bunkbed conjecture","percolation","biconnected components","cactus graphs","graph minors","diamond graph","strong bunkbed conjecture","block decomposition"],"falsifier":"Enumerate all biconnected graphs on five through eight vertices and check whether every one that is not a cycle contains one of the two diamond-subdivision graphs of Theorem 4 as a minor; a single non-cycle avoiding both would falsify the classification lemma on which Theorem 4 rests.","tokens_in":15902,"feed_emoji":"🌵","tokens_out":9093,"duration_ms":93346,"temperature":0.7,"pith_summary":"The paper proves that the bunkbed conjecture, a 1985 conjecture comparing connection probabilities in a two-layer random graph, can be checked block by block: a graph satisfies the weak or strong version if and only if every one of its biconnected components does. Using this reduction, the paper establishes that all cactus graphs satisfy the strong version, and more generally that any graph whose blocks are cycles or have at most four vertices satisfies the strong version. It also extends known weak-version results to graphs whose blocks are cycles, complete graphs, complete bipartite graphs, symmetric complete $k$-partite graphs, or edge differences of a complete graph and a complete subgraph. Because the conjecture is known to fail in general, the paper uses the block reduction to constrain counterexamples: any counterexample to the strong version must contain one of the two smallest non-trivial subdivisions of the diamond graph as a minor, and the minimal counterexamples form a finite set of biconnected graphs.","feed_headline":"Bunkbed conjecture holds for every cactus graph","feed_subtitle":"Graphs split into biconnected blocks; cycles and small blocks are all that stand between.","key_machinery":"The central object is the bunkbed graph $B(G)$: two copies of $G$ connected by vertical posts, with horizontal edges percolating independently. The mechanism carrying the argument is block decomposition combined with a gluing lemma (Theorem 1b): if two graphs share exactly one vertex, the conjecture holds for their union exactly when it holds for each part. The proof of the gluing lemma uses the mirror symmetry between the two bunks, Harris's inequality for the one-post case, an edge-deletion lemma that adds a direct edge between the terminal vertices, and a boundary lemma showing equal probabilities when a set of terminals separates the two vertices; repeated application over a vertex cut then reduces the whole graph to its biconnected components. The minor-obstruction part is carried by the graph minor theorem together with a classification of the relevant four-vertex block class.","core_discovery":"On the paper's own terms, the central theorem states that for any graph $G$ and any percolation vector $\\vec p$ on its edges, the inequality $B(G,T,\\vec p,v,w)$ — that $v_0$ connects to $w_0$ at least as often as to $w_1$ in the random bunkbed subgraph — holds for all terminal sets $T$ and pairs $v,w$ if and only if the corresponding inequality holds inside every biconnected component of $G$. The paper derives this from a gluing lemma for two graphs identified at a single vertex and applies it in two directions. For the strong version, it proves Theorem 2 that every cactus graph satisfies the strong bunkbed conjecture, and Theorem 11 that every graph whose biconnected components are cycles or have at most four vertices does as well. For the weak version, it proves Theorem 3 combining known results for complete and complete multipartite type blocks. Finally, Theorem 4 shows every counterexample to the strong version contains the diamond graph, more specifically one of the two smallest non-trivial subdivisions of the diamond graph, as a minor; Theorem 13 upgrades this to a finite forbidden-minor characterization.","pith_inferences":["Because the block reduction is exact, a counterexample search can be restricted to biconnected graphs: any failure in a larger graph would show up inside one block.","The finite forbidden-minor set promised by Theorem 13 implies that, in principle, deciding the strong conjecture for a given graph is a finite computation against a fixed list of minor obstructions, although producing that list may be enormous.","The 'easy to see' minor classification of biconnected graphs with more than four vertices is the part most worth verifying independently; a computational check over small biconnected graphs would settle whether the diamond-subdivision obstruction is complete."],"forward_implications":["Every cactus graph satisfies the strong bunkbed conjecture, and more generally every graph whose blocks are cycles or have at most four vertices does as well.","Any graph whose biconnected components are cycles, complete graphs, complete bipartite graphs, symmetric complete $k$-partite graphs, or edge differences of a complete graph and a complete subgraph satisfies the weak bunkbed conjecture.","If the strong conjecture is proved for the complete graph $K_n$ for any $5 \\le n \\le 7221$, then the allowed blocks in Theorem 11 expand from at most four vertices to at most $n$ vertices; the known counterexample with 7222 vertices shows this route cannot go beyond $n=7221$.","Every counterexample to the strong conjecture contains a non-trivial subdivision of the diamond graph as a minor, and the minimal counterexamples are biconnected.","The minimal counterexamples to the strong conjecture form a finite set under the minor relation, so the class of graphs satisfying the strong conjecture is minor-closed and finitely characterized."],"supporting_citations":[{"why":"Supplies the 7222-vertex counterexample that makes the conjecture false; Theorem 13's non-empty forbidden set and the bound n≤7221 rely on it.","marker":"[GPZ24]"},{"why":"Proves the weak bunkbed conjecture for complete graphs, one of the block classes in Theorem 3.","marker":"[HL19]"},{"why":"Proves the weak conjecture for complete bipartite and related graph classes, extending the block list in Theorem 3.","marker":"[Ric22]"},{"why":"Harris's inequality is used in Lemma A to handle the single-post case, supporting the cycle and diamond proofs.","marker":"[Har60]"},{"why":"Identifies the diamond graph as the forbidden minor for cactus graphs, anchoring the minor classification used in Theorem 4.","marker":"[EC88]"},{"why":"The graph minor theorem underlies Theorem 13's finite forbidden-minor characterization.","marker":"[RS04]"}],"fun_headline_variants":["Cactus graphs keep bunkbed conjecture intact","Bunkbed conjecture: cactus graphs satisfy","Biconnected components settle bunkbed cases","All cactus graphs obey bunkbed conjecture","Cactus and small blocks: bunkbed holds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The classification step that every biconnected graph with more than four vertices that is not a cycle contains one of the two specified diamond subdivisions as a minor — asserted as 'easy to see' with only a sketch — must be true for Theorems 4 and 13.","fun_headline_variants_meta":{"raw":{"variants":["Cactus graphs keep bunkbed conjecture intact","Bunkbed conjecture: cactus graphs satisfy","Biconnected components settle bunkbed cases","All cactus graphs obey bunkbed conjecture","Cactus and small blocks: bunkbed holds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000339,"raw_usage":{"total_tokens":1894,"prompt_tokens":990,"completion_tokens":904,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":837}},"tokens_in":606,"tokens_out":904,"duration_ms":10434,"temperature":1.0,"reasoning_tokens":837,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:54:35.747069+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all biconnected graphs on five through eight vertices and check whether every one that is not a cycle contains one of the two diamond-subdivision graphs of Theorem 4 as a minor; a single non-cycle avoiding both would falsify the classification lemma on which Theorem 4 rests.","supporting_citations":[],"review_version":1}