Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The gadget GnG_nGn​ has 2n−12n-12n−1 edges

Proved
BunkbedAux.gadgetE_card

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

bunkbedcombinatoricsgraph-theorypercolation

The gadget GnG_nGn​ of Gladkov--Pak--Zimin (Figure 2) has vertex set {0,1,…,n}\{0, 1, \dots, n\}{0,1,…,n} and consists of a path v1−v2−⋯−vnv_1 - v_2 - \cdots - v_nv1​−v2​−⋯−vn​ on the vertices 1,…,n1, \dots, n1,…,n, together with a hub a=0a = 0a=0 joined to every path vertex. It is the graph used to simulate a 333-hyperedge, with the three distinguished vertices being the hub and the two ends of the path.

This theorem counts its edges:

∣E(Gn)∣  =  2n−1,|E(G_n)| \;=\; 2n - 1,∣E(Gn​)∣=2n−1,

namely the nnn spokes {0,vj}\{0, v_j\}{0,vj​} for 1≤j≤n1 \le j \le n1≤j≤n, plus the n−1n - 1n−1 path edges {vi,vi+1}\{v_i, v_{i+1}\}{vi​,vi+1​} for 1≤i≤n−11 \le i \le n-11≤i≤n−1.

The proof splits the edge set into those two families, shows each has the stated size, and shows they are disjoint — a spoke is incident to the hub and a path edge is not.

Mathematical role. This is the combinatorial input to the edge count of the counterexample graph of Theorem 1.2. That graph substitutes a copy of G1204G_{1204}G1204​ for each of the six hyperedges of Hollom's hypergraph, and the six copies are edge-disjoint, so its edge count is

6⋅(2⋅1204−1)  =  6⋅2407  =  14,442,6 \cdot (2 \cdot 1204 - 1) \;=\; 6 \cdot 2407 \;=\; 14{,}442,6⋅(2⋅1204−1)=6⋅2407=14,442,

which is the figure appearing in the statement of Theorem 1.2.

Preamble
import Definitions.Def_BunkbedPercolation
open Bunkbed SimpleGraph Finset
Formal statement
namespace BunkbedAux

/-- **The gadget `Gₙ` has `2n - 1` edges**: `n` spokes from the apex to each path vertex, and
`n - 1` path edges. -/
theorem gadgetE_card (n : ℕ) : (gadgetE n).card = 2 * n - 1 := by
  sorry

end BunkbedAux
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, Figure 2 (p. 6) and Section 4.2 (p. 7), where the edge count 6*2407 = 14442 of the counterexample graph is stated.

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