Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The substituted graph has 14442 edges, three transversal vertices, and is connected

Proved
BunkbedFalse.sub_invariants

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

bunkbedcombinatoricsgraph-theorypercolation

Theorem 1.2 of Gladkov--Pak--Zimin asserts the existence of a connected graph on 7,2227{,}2227,222 vertices with 14,44214{,}44214,442 edges and a transversal set of size three, on which bunkbed percolation at P=1/2P = 1/2P=1/2 violates the conjecture. This theorem establishes the three combinatorial assertions for the explicit graph constructed by substituting a copy of the gadget G1204G_{1204}G1204​ for each of the six hyperedges of Hollom's hypergraph.

  1. Edge count. ∣E∣=14,442|E| = 14{,}442∣E∣=14,442. The six embedded copies are pairwise disjoint, each copy is an injective image of G1204G_{1204}G1204​, and GnG_nGn​ has 2n−12n-12n−1 edges, so the total is 6⋅2407=14,4426 \cdot 2407 = 14{,}4426⋅2407=14,442. Since no embedded edge is a loop, the number of edges of the graph agrees with the cardinality of the edge set.

  2. Transversal set. ∣T∣=3|T| = 3∣T∣=3, being the injective image of hollomT={u2,u7,u9}\texttt{hollomT} = \{u_2, u_7, u_9\}hollomT={u2​,u7​,u9​}. Three is the smallest number of transversal vertices for which the bunkbed conjecture can fail.

  3. Connectivity. Each gadget copy is connected, because its apex is adjacent to every one of its path vertices. The copies are then glued along the path u1,u3,u6,u5,u4,u8,u10u_1, u_3, u_6, u_5, u_4, u_8, u_{10}u1​,u3​,u6​,u5​,u4​,u8​,u10​: copy iii contains both the iii-th and the (i+1)(i+1)(i+1)-st vertex of that path. So every vertex reaches u1u_1u1​ — first by moving inside its own copy to that copy's apex or path end, then by walking down the chain of copies.

Mathematical role. Together with the identification of bunkbed percolation on this graph as a Wierman--Ziff model on Hollom's hypergraph, and the verification that the gadget's partition probabilities satisfy the conditions of the robustness lemma, these three facts complete Theorem 1.2. Note that the published Theorem 1.2 also asserts planarity; that cannot presently be stated, as Mathlib has no notion of a planar graph, so the formalised statement is weaker in that respect.

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

/-- **The invariants of the substituted graph.** It has 14442 edges, its transversal set has three
vertices, and it is connected. -/
theorem sub_invariants :
    (ofEdges Bunkbed.Sub.subEdges).edgeFinset.card = 14442 ∧ Bunkbed.Sub.subT.card = 3
      ∧ (ofEdges Bunkbed.Sub.subEdges).Connected := by
  sorry

end BunkbedFalse
Source
N. Gladkov, I. Pak, A. Zimin, The bunkbed conjecture is false, PNAS 122 (2025) no. 24, e2420725122, https://doi.org/10.1073/pnas.2420725122, Theorem 1.2 (p. 1) and Section 4.2 (p. 7).

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