Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.2 — explicit counterexample on 7,222 vertices (planarity omitted)

Proved
BunkbedFalse.explicit_counterexample

by burkh4rt · Sep 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theorypercolationprobability

There exists a connected graph G=(V,E)G = (V,E)G=(V,E) with ∣V∣=7,222|V| = 7{,}222∣V∣=7,222 vertices and ∣E∣=14,442|E| = 14{,}442∣E∣=14,442 edges, a transversal set T⊂VT \subset VT⊂V with exactly three vertices, and vertices u,v∈Vu, v \in Vu,v∈V, such that in bunkbed percolation at P=1/2P = 1/2P=1/2,

P1/2bb[u↔v]  <  P1/2bb[u↔v′].\mathbb{P}^{\mathrm{bb}}_{1/2}\bigl[u \leftrightarrow v\bigr] \;<\; \mathbb{P}^{\mathrm{bb}}_{1/2}\bigl[u \leftrightarrow v'\bigr].P1/2bb​[u↔v]<P1/2bb​[u↔v′].

The graph is obtained by taking Hollom's hypergraph and substituting the gadget GnG_nGn​ with n=3⋅401+1=1204n = 3 \cdot 401 + 1 = 1204n=3⋅401+1=1204 for each of its six 333-hyperedges, placing the gadget so that its apex aaa is the transversal vertex; this yields 10+6⋅1202=7,22210 + 6 \cdot 1202 = 7{,}22210+6⋅1202=7,222 vertices and 6⋅2407=14,4426 \cdot 2407 = 14{,}4426⋅2407=14,442 edges. Three is the smallest number of transversal vertices for which the conjecture can fail.

The probability gap is tiny — the source estimates it at less than 10−433110^{-4331}10−4331 — so no computational search could have detected it; the argument is entirely structural.

Formalization Note ⚠️ The published Theorem 1.2 also asserts that GGG is planar, and that assertion is omitted here: Mathlib has no notion of a planar graph, so the property cannot currently be stated. The formalized statement is therefore strictly weaker than the published one. Adding planarity would be a welcome strengthening. The vertex count is carried by the carrier type Fin 7222.

Formalization Note (edge count). The edge count is stated as (ofEdges E).edgeFinset.card = 14442, i.e. the number of edges of the graph, rather than the cardinality of the defining Finset (Sym2 _). The two differ: Sym2 contains diagonal pairs {x,x}\{x,x\}{x,x}, which fromEdgeSet silently discards, so constraining the raw Finset would have pinned the true edge count only to the range [7221,14442][7221, 14442][7221,14442].

Preamble
import Definitions.Def_BunkbedHypergraph
open Bunkbed Bunkbed.Hyper SimpleGraph Finset
Formal statement
namespace BunkbedFalse

/-- **Theorem 1.2** (p. 1), with the planarity assertion omitted: Mathlib has no notion of a
planar graph. -/
theorem explicit_counterexample :
    ∃ (E : Finset (Sym2 (Fin 7222))) (T : Finset (Fin 7222)) (u v : Fin 7222),
      (ofEdges E).edgeFinset.card = 14442 ∧ T.card = 3 ∧ (ofEdges E).Connected ∧
      bbProb E (fun _ => (1 / 2 : ℚ)) T (u, 0) (v, 0)
        < bbProb E (fun _ => (1 / 2 : ℚ)) T (u, 0) (v, 1) := by sorry

end BunkbedFalse
Source
N. Gladkov, I. Pak, A. Zimin, "The bunkbed conjecture is false", Proc. Natl. Acad. Sci. USA 122 (2025), no. 24, e2420725122, https://doi.org/10.1073/pnas.2420725122 - p. 1, Theorem 1.2; proof p. 7 (Section 4.2). Planarity omitted: absent from Mathlib.
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back — BunkbedFalse.explicit_counterexample

What is asserted

The declaration is a bare existential statement with no hypotheses and no parameters. It asserts that there exist

  • a finite set EEE of unordered pairs of elements of V={0,1,…,7221}V=\{0,1,\dots,7221\}V={0,1,…,7221} (the type Fin 7222\mathrm{Fin}\,7222Fin7222), i.e. EEE is a finite set of symmetric pairs {x,y}\{x,y\}{x,y}, possibly including diagonal pairs {x,x}\{x,x\}{x,x};
  • a subset T⊆VT\subseteq VT⊆V;
  • two elements u,v∈Vu,v\in Vu,v∈V;

such that all four of the following hold simultaneously.

Write G=G(E)G=G(E)G=G(E) for the simple graph on the vertex set VVV (all 722272227222 elements) in which

x∼Gy  ⟺  {x,y}∈E  and  x≠y.x\sim_G y \iff \{x,y\}\in E \ \text{ and }\ x\neq y .x∼G​y⟺{x,y}∈E  and  x=y.

(The construction is Mathlib's fromEdgeSet, so any diagonal pair {x,x}\{x,x\}{x,x} present in EEE is silently discarded and produces no loop.)

(1) Edge count.

# Edges(G)=14442.\#\,\mathrm{Edges}(G)=14442 .#Edges(G)=14442.

This counts the edges of the graph GGG, i.e. the number of off-diagonal pairs in EEE. It is not ∣E∣|E|∣E∣: the cardinality of the data EEE is left completely unconstrained above 144421444214442, because EEE may additionally contain any of the 722272227222 diagonal pairs {x,x}\{x,x\}{x,x}, so 14442≤∣E∣≤2166414442 \le |E| \le 2166414442≤∣E∣≤21664 is permitted while the graph-edge count is pinned to exactly 144421444214442. (Verified by computation on a 444-cycle: adding two diagonal pairs to EEE left the graph's edge count at 444 while ∣E∣|E|∣E∣ became 666, and left every probability below unchanged.)

(2) Post count. ∣T∣=3|T|=3∣T∣=3 exactly.

(3) Connectivity. GGG is connected in Mathlib's sense: VVV is nonempty (automatic, 7222>07222>07222>0) and every ordered pair of vertices is joined by a walk. Because the vertex type is all of Fin 7222\mathrm{Fin}\,7222Fin7222, connectivity is required on all 722272227222 vertices; no isolated or unused vertices are allowed, so the vertex count is genuinely pinned at 722272227222 by the type together with this condition.

(4) A strict reversal of the bunkbed inequality at p=12p=\tfrac12p=21​.

bb((u,0),(v,0))  <  bb((u,0),(v,1)).\mathrm{bb}\big((u,0),(v,0)\big)\;<\;\mathrm{bb}\big((u,0),(v,1)\big).bb((u,0),(v,0))<bb((u,0),(v,1)).

Unfolding the probability bb\mathrm{bb}bb

For a subset S⊆ES\subseteq ES⊆E the configuration weight with the constant edge-weight function w(e)=12w(e)=\tfrac12w(e)=21​ for every eee is

wt(S)=(∏e∈S12)(∏e∈E∖S(1−12))=2−∣E∣,\mathrm{wt}(S)=\Big(\prod_{e\in S} \tfrac12\Big)\Big(\prod_{e\in E\setminus S}\big(1-\tfrac12\big)\Big)=2^{-|E|},wt(S)=(e∈S∏​21​)(e∈E∖S∏​(1−21​))=2−∣E∣,

so ∑S⊆Ewt(S)=1\sum_{S\subseteq E}\mathrm{wt}(S)=1∑S⊆E​wt(S)=1 (checked numerically, with and without diagonal pairs in EEE): this is honest Bernoulli(12\tfrac1221​) bond percolation on EEE.

Given two open sets S0,S1⊆ES_0,S_1\subseteq ES0​,S1​⊆E, the bunkbed graph B(T,S0,S1)B(T,S_0,S_1)B(T,S0​,S1​) is the simple graph on V×{0,1}V\times\{0,1\}V×{0,1} (so 144441444414444 vertices) whose edges are exactly

{(x,0),(y,0)}  for {x,y}∈S0,{(x,1),(y,1)}  for {x,y}∈S1,{(t,0),(t,1)}  for t∈T,\{(x,0),(y,0)\}\ \text{ for }\{x,y\}\in S_0,\qquad \{(x,1),(y,1)\}\ \text{ for }\{x,y\}\in S_1,\qquad \{(t,0),(t,1)\}\ \text{ for } t\in T,{(x,0),(y,0)}  for {x,y}∈S0​,{(x,1),(y,1)}  for {x,y}∈S1​,{(t,0),(t,1)}  for t∈T,

the three vertical posts over TTT being present with probability 111 in every configuration. Then

bb(x,y)  =  ∑S0⊆E ∑S1⊆E1[x↔y in B(T,S0,S1)]⋅wt(S0)⋅wt(S1)  =  4−∣E∣⋅#{(S0,S1):x↔y},\mathrm{bb}(x,y)\;=\;\sum_{S_0\subseteq E}\ \sum_{S_1\subseteq E}\mathbf 1\big[x \leftrightarrow y \text{ in } B(T,S_0,S_1)\big]\cdot \mathrm{wt}(S_0)\cdot\mathrm{wt}(S_1)\;=\;4^{-|E|}\cdot\#\big\{(S_0,S_1): x\leftrightarrow y\big\},bb(x,y)=S0​⊆E∑​ S1​⊆E∑​1[x↔y in B(T,S0​,S1​)]⋅wt(S0​)⋅wt(S1​)=4−∣E∣⋅#{(S0​,S1​):x↔y},

where ↔\leftrightarrow↔ is reachability (reflexive: x↔xx\leftrightarrow xx↔x always). The two levels are percolated independently with the same law; both sides of (4) use the same EEE, the same weight 12\tfrac1221​, the same TTT, and the same source vertex (u,0)(u,0)(u,0).

Which side is smaller, and which levels are compared

  • Left-hand side: uuu and vvv both in the bottom level 000 — the same-level connection probability.
  • Right-hand side: source (u,0)(u,0)(u,0) in the bottom level, target (v,1)(v,1)(v,1) in the top level — the opposite-level connection probability.
  • The strict inequality makes the same-level probability the strictly smaller of the two. (The bunkbed conjecture as recorded in the same definition bundle asserts  bb((u,0),(v,0))≥bb((u,0),(v,1))\ \mathrm{bb}((u,0),(v,0)) \ge \mathrm{bb}((u,0),(v,1)) bb((u,0),(v,0))≥bb((u,0),(v,1)) for all connected graphs, all TTT and all 0<p<10<p<10<p<1; the statement here asserts the opposite strict inequality for some explicit datum at p=12p=\tfrac12p=21​, and 12\tfrac1221​ does lie in (0,1)(0,1)(0,1).)

Numerical consistency of the stated counts

A connected simple graph on 722272227222 vertices needs at least 722172217221 edges and admits at most (72222)=26 075 031\binom{7222}{2}=26\,075\,031(27222​)=26075031; the required 14442=2⋅722114442=2\cdot 722114442=2⋅7221 lies strictly between, so (1)+(3) are mutually satisfiable. The average degree is 2⋅14442/7222=28884/7222≈3.999452\cdot 14442/7222 = 28884/7222 \approx 3.999452⋅14442/7222=28884/7222≈3.99945, i.e. just short of 444-regular (444-regularity on 722272227222 vertices would require 144441444414444 edges, so the graph cannot be 444-regular). The bunkbed graph then has 144441444414444 vertices and at most 2⋅14442+3=288872\cdot 14442+3=288872⋅14442+3=28887 edges. The percolation sum ranges over 4∣E∣≥4144424^{|E|}\ge 4^{14442}4∣E∣≥414442 configuration pairs, so neither side can be evaluated directly; all claims below were settled on small analogues instead.

Degenerate routes are closed — what the existential cannot be met by

Each of the following would collapse (4), so the statement implicitly forces them to be avoided:

  • u=vu=vu=v is impossible. Reachability is reflexive, so the indicator on the left is 111 in every configuration and the left side equals exactly 111, while the right side is at most 111; a strict <<< then fails. (Computed on the 444-cycle with T={0}T=\{0\}T={0}: bb((1,0),(1,0))=1\mathrm{bb}((1,0),(1,0))=1bb((1,0),(1,0))=1 versus bb((1,0),(1,1))=81/256\mathrm{bb}((1,0),(1,1))=81/256bb((1,0),(1,1))=81/256.) So u≠vu\neq vu=v is a consequence of (4).
  • v∈Tv\in Tv∈T is impossible. The post {(v,0),(v,1)}\{(v,0),(v,1)\}{(v,0),(v,1)} is always open, so (v,0)(v,0)(v,0) and (v,1)(v,1)(v,1) lie in the same component in every configuration and the two sides are identically equal. (Computed: 444-cycle, T={0,2}T=\{0,2\}T={0,2}, u=1u=1u=1, v=2v=2v=2 gives 165/256165/256165/256 on both sides.) So v∉Tv\notin Tv∈/T.
  • u∈Tu\in Tu∈T is also impossible. Swapping the two levels is a weight-preserving involution of the configuration space, giving bb((u,0),(v,1))=bb((u,1),(v,0))\mathrm{bb}((u,0),(v,1))=\mathrm{bb}((u,1),(v,0))bb((u,0),(v,1))=bb((u,1),(v,0)); if u∈Tu\in Tu∈T then (u,0)(u,0)(u,0) and (u,1)(u,1)(u,1) are always in the same component, so the right side equals the left. (Computed: 444-cycle, T={0,2}T=\{0,2\}T={0,2}, u=0u=0u=0, v=1v=1v=1 gives 165/256165/256165/256 on both sides.) So u∉Tu\notin Tu∈/T, and u,vu,vu,v must be two distinct vertices among the 721972197219 outside TTT.
  • Both sides zero is impossible, since <<< forces the right side to be strictly positive. The left side is automatically strictly positive: (3) makes GGG connected, so the configuration S0=S1=ES_0=S_1=ES0​=S1​=E (which carries weight 4−∣E∣>04^{-|E|}>04−∣E∣>0) already connects (u,0)(u,0)(u,0) to (v,0)(v,0)(v,0); hence bb((u,0),(v,0))≥4−∣E∣>0\mathrm{bb}((u,0),(v,0))\ge 4^{-|E|}>0bb((u,0),(v,0))≥4−∣E∣>0 and the assertion is that a strictly positive quantity is strictly exceeded.
  • No empty or postless degeneracy. ∣T∣=3|T|=3∣T∣=3 rules out T=∅T=\emptysetT=∅ (with T=∅T=\emptysetT=∅ the opposite-level probability is identically 000 — computed as 000 on the 444-cycle — so (4) would fail), and E=∅E=\emptysetE=∅ or any disconnected/spanning-deficient structure is ruled out by (1) and (3).
  • Diagonal padding is inert, not exploitable. Adding pairs {x,x}\{x,x\}{x,x} to EEE enlarges the powerset sums but changes neither graph nor probabilities (computed: 7/167/167/16 and 81/25681/25681/256 before and after adding two diagonal pairs), so it can only slacken the reading of "∣E∣|E|∣E∣", never the inequality (4).
  • For reference, on the small analogues tested the inequality ran the other way (same-level 7/16=112/2567/16=112/2567/16=112/256 versus opposite-level 81/25681/25681/256), consistent with the reversal in (4) not being attainable by a small or generic structure.

Summary of every numeric constant appearing

Vertex type Fin 7222\mathrm{Fin}\,7222Fin7222 (722272227222 base vertices, 144441444414444 bunkbed vertices); graph-edge count exactly 144421444214442; ∣T∣|T|∣T∣ exactly 333; every edge open independently with probability exactly 1/21/21/2 (the rational 1/21/21/2, on both levels, with the identical weight function on both sides); posts over TTT open with probability 111; levels indexed by 000 (bottom) and 111 (top); the compared pairs are ((u,0),(v,0))\big((u,0),(v,0)\big)((u,0),(v,0)) and ((u,0),(v,1))\big((u,0),(v,1)\big)((u,0),(v,1)), with strict inequality <<< (not ≤\le≤, not ≠\neq=), and existence only (not uniqueness). No constraint is imposed on ∣E∣|E|∣E∣ itself, on the degree sequence, on the girth, or on the identity of TTT, uuu, vvv beyond ∣T∣=3|T|=3∣T∣=3.

Human review
  • Endorsed by Shuze Chen · Sep 11, 2026

  • Endorsed by burkh4rt · Sep 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me