Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.2, p. 3:14 — at most N neighbourhoods and N+1 vertices force two twins across the cut

Proved
TwinWidthI.BoolWidth.exists_same_nbhd

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

boolean-widthp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1twin-width

Let GGG be a finite simple graph on VVV, let A,B⊆VA,B\subseteq VA,B⊆V be disjoint, and let N≥0N\ge 0N≥0. Suppose the number of different neighbourhoods in BBB of subsets of AAA is at most NNN,

νG(A,B)=∣{N(S)∩B:S⊆A}∣≤N,\nu_G(A,B)=\bigl|\{N(S)\cap B: S\subseteq A\}\bigr|\le N,νG​(A,B)=​{N(S)∩B:S⊆A}​≤N,

and ∣A∣≥N+1|A|\ge N+1∣A∣≥N+1. Then there are two distinct vertices u≠vu\neq vu=v in AAA with the same neighbourhood in BBB: for every b∈Bb\in Bb∈B, ububub is an edge if and only if vbvbvb is an edge.

In the proof of Theorem 4.2 this is applied to the cut Pe=(Ae,Be)P_e=(A_e,B_e)Pe​=(Ae​,Be​) of boolean-width at most kkk, with N=2kN=2^kN=2k and ∣Ae∣≥2k+1|A_e|\ge 2^k+1∣Ae​∣≥2k+1; the two vertices u,vu, vu,v are the first pair to be contracted.

Formalization Note. νG(A,B)\nu_G(A,B)νG​(A,B) is nbhdCount G A B, which counts neighbourhoods of all subsets of AAA, including the empty set.

Preamble
import Mathlib
import Definitions.Def_TwinWidthI_BoolWidth_Setting
Formal statement
namespace TwinWidthI.BoolWidth

open Finset

theorem exists_same_nbhd {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (A B : Finset V) (hAB : Disjoint A B) (N : ℕ)
    (hcount : nbhdCount G A B ≤ N) (hA : N + 1 ≤ #A) :
    ∃ u ∈ A, ∃ v ∈ A, u ≠ v ∧ ∀ b ∈ B, (G.Adj u b ↔ G.Adj v b) := by sorry

end TwinWidthI.BoolWidth
Source
Bonnet, Kim, Thomassé and Watrigant, Twin-width I: Tractable FO Model Checking, J. ACM 69(1), Article 3 (2021), p. 3:14, proof of Theorem 4.2, "among the 2^k + 1 leaves of T′, corresponding to, say, A_e, two vertices u,v have the same neighborhood in B_e"
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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