REVIEW 2 major objections 6 minor 3 references
The bunkbed conjecture still holds for cactus graphs and for graphs with certain biconnected components
T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (2)
- [Section 2, proof of Theorem 4] 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 2, proof of Theorem 13] 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.
minor comments (6)
- [Introduction, countable-graph remark] 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.
- [Theorem 4 statement] 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 2, Lemma B] 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 2, Lemma B] 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.
- [Throughout] There are several typographical errors: 'seperately', 'atleast', 'adressed', and 'en' (in the proof of Theorem 1) should be corrected.
- [Section 2, Proposition 8] 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.
Circularity Check
No circularity: main theorems are proved from the bunkbed definitions via gluing, monotonicity, and percolation lemmas; Theorem 4's unproved minor classification is a proof gap, not a circular reduction.
full rationale
The derivation is self-contained: no fitted parameters exist, no quantity is predicted from data, and none of the ten references is authored by Denart, so the paper contains no self-citation at all. The central block decomposition (Theorem 1) is proved from Theorem 1b (gluing two graphs at one vertex), whose "if" and "only if" directions are established by explicit probability decompositions and mirroring arguments that use only the definition of the bunkbed graph, edge-independent weights, and independence of the two induced random graphs; Theorem 1 then follows by induction on |V(G)| using the fact that every edge lies in exactly one block, with no input equivalent to the conclusion. Theorem 2 (cactus graphs) reduces, via Theorem 1 and Proposition 8 (blocks of a cactus are K2 or cycles), to Example 5 (K2, using Lemma A, which cites Harris' inequality [Har60] as an external standard fact) and Proposition 7 (cycles, using Lemma B and Proposition 6). Lemma B is proved in full inside the paper by a term-by-term Q(W) decomposition under the conditioning event A; it is not imported by citation. Proposition 9 (diamond) and Proposition 10 (K4) are proved after Theorem 2 and use it, so the lemma order is acyclic. Theorem 3 explicitly delegates the complete, complete bipartite, symmetric complete k-partite and edge-difference cases to the independent external results [HL19] and [Ric22], and Theorem 13 invokes the external graph minor theorem [RS04] and the external counterexample [GPZ24]; the footnote about overlapping work [MP24] concerns special cases of Theorem 1b for which the paper gives a complete independent proof, so it creates no load-bearing citation.
Assumptions & free parameters
assumptions (4)
- standard math Harris' inequality for increasing events on finite product spaces
- standard math Graph minor theorem (Robertson-Seymour): every minor-closed class of finite graphs has a finite set of forbidden minors
- domain assumption Weak bunkbed conjecture holds for complete graphs, complete bipartite graphs, symmetric complete k-partite graphs, and edge differences of a complete graph and a complete subgraph ([HL19], [Ric22])
- domain assumption The bunkbed conjecture is false in general; there exists a finite counterexample ([GPZ24])
Cite this review
Pith. "Pith review of The bunkbed conjecture still holds for cactus graphs and for graphs with certain biconnected components." pith.science (2026). https://pith.science/paper/HQRXWM65
@misc{pith2026250609264,
author = {Pith},
title = {Pith review of: The bunkbed conjecture still holds for cactus graphs and for graphs with certain biconnected components},
year = {2026},
howpublished = {\url{https://pith.science/paper/HQRXWM65}},
note = {Machine review of arXiv:2506.09264}
}
abstract
Recently, the bunkbed conjecture has been shown to be false, which naturally prompts questions on how to classify the graphs that still satisfy the conjecture. We distinguish between a weak version of the bunkbed conjecture where all the horizontal edges of the bunkbed graph are present with the same probability and a strong version of the conjecture where the edge weights on the underlying graph may be assigned individually. We show that any given graph satisfies either version of the conjecture if and only if all of its biconnected components do. Moreover, we show that all cactus graphs satisfy the strong version, and by combining previous results of other authors, any graph $G$ such that every biconnected component of $G$ is either a cycle, complete, complete bipartite, symmetric complete $k$-partite or an edge difference of a complete graph and a complete subgraph satisfies the weak version. Furthermore, we apply the aforementioned results to show that any counterexample to the strong version of the bunkbed conjecture contains a non-trivial subdivision of the diamond graph as a minor and demonstrate how this result might be strengthened in the future.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
The complexity of some edge deletion problems
[EC88] Ehab S El-Mallah and Charles J Colbourn. “The complexity of some edge deletion problems”. In: IEEE transactions on circuits and systems 35.3 (1988), pp. 354–
work page 1988
-
[3]
The bunkbed conjecture is not robust to generalisation
Cambridge University Press. 1960, pp. 13–20. [HKN23] Tom Hutchcroft, Alexander Kent, and Petar Nizi´ c-Nikolac. “The bunkbed con- jecture holds in the p ↑1 limit”. In: Combinatorics, Probability and Computing 32.3 (2023), pp. 363–369. [HL19] Peter van Hintum and Piet Lammers. “The bunkbed conjecture on the complete graph”. In: European Journal of Combinat...
work page Pith review arXiv 2023
-
[362]
The bunkbed conjecture is false
[GPZ24] Nikita Gladkov, Igor Pak, and Aleksandr Zimin. “The bunkbed conjecture is false”. In: arXiv preprint arXiv:2410.02545 (2024). [Har60] Theodore E Harris. “A lower bound for the critical probability in a certain per- colation process”. In: Mathematical Proceedings of the Cambridge Philosophical Society. Vol
work page Pith review arXiv 2024
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.