Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Neighbour closure computes the reachable set

Proved
FastReach.mem_reachSet_iff

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

combinatoricsgraph-theoryutility

Let GGG be a simple graph on a finite vertex type VVV with decidable adjacency, and recall the neighbour-closure operator

step⁡(s)  =  s  ∪  { v∈V  :  ∃ u∈s, u∼Gv },\operatorname{step}(s) \;=\; s \;\cup\; \{\, v \in V \;:\; \exists\, u \in s,\ u \sim_G v \,\},step(s)=s∪{v∈V:∃u∈s, u∼G​v},

together with reachSet⁡(u)=step⁡ ∣V∣({u})\operatorname{reachSet}(u) = \operatorname{step}^{\,|V|}(\{u\})reachSet(u)=step∣V∣({u}). This theorem asserts that the construction is correct: for all vertices u,vu, vu,v,

v∈reachSet⁡(u)⟺v is reachable from u in G.v \in \operatorname{reachSet}(u) \quad\Longleftrightarrow\quad v \text{ is reachable from } u \text{ in } G.v∈reachSet(u)⟺v is reachable from u in G.

The forward direction is a straightforward induction on the number of rounds: {u}\{u\}{u} consists of vertices reachable from uuu, and each round only adds vertices adjacent to something already known to be reachable, so reachability is preserved throughout.

The reverse direction needs the iteration count to be large enough. If vvv is reachable from uuu then some path joins them, and a path in a finite graph has length strictly less than ∣V∣|V|∣V∣, since its vertices are distinct. An induction along that path shows that its endpoint lies in the ℓ\ellℓ-th closure where ℓ\ellℓ is the path's length; because step⁡\operatorname{step}step is inflationary the closures are nested increasing, so the endpoint also lies in the ∣V∣|V|∣V∣-th closure. Taking a path rather than an arbitrary walk is what makes the fixed iteration count ∣V∣|V|∣V∣ sufficient.

The value of this statement is practical. It licenses replacing Mathlib's decision procedure for SimpleGraph.Reachable — which searches over all walks of length less than ∣V∣|V|∣V∣ and is unusable past roughly ten vertices — by a Finset computation that evaluates directly. Any argument that needs to settle connectivity in a concrete finite graph, or to sum a quantity over configurations of a percolation weighted by whether two vertices are connected, can use it.

Formalization Note The statement is universally quantified over the vertex type, the graph, the adjacency-decidability instance and the two vertices, all implicit. Reachability is Mathlib's SimpleGraph.Reachable, i.e. Nonempty (G.Walk u v), which is reflexive; correspondingly u∈reachSet⁡(u)u \in \operatorname{reachSet}(u)u∈reachSet(u) holds because the zeroth closure is {u}\{u\}{u}.

Preamble
import Definitions.Def_FastReachability
Formal statement
namespace FastReach

/-- Neighbour closure iterated `|V|` times computes exactly the reachable set. -/
theorem mem_reachSet_iff {V : Type*} [Fintype V] [DecidableEq V]
    {G : SimpleGraph V} [DecidableRel G.Adj] {u v : V} :
    v ∈ reachSet G u ↔ G.Reachable u v := by sorry

end FastReach
Source
Standard correctness statement for breadth-first / neighbour-closure reachability. Companion to the definition FastReachability; motivated by the infeasibility of Mathlib reachable_iff_exists_finsetWalkLength_nonempty (Mathlib/Combinatorics/SimpleGraph/Connectivity/Finite.lean) on graphs of more than ~10 vertices.

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