Neighbour closure computes the reachable set
ProvedFastReach.mem_reachSet_iffLet be a simple graph on a finite vertex type with decidable adjacency, and recall the neighbour-closure operator
together with . This theorem asserts that the construction is correct: for all vertices ,
The forward direction is a straightforward induction on the number of rounds: consists of vertices reachable from , 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 is reachable from then some path joins them, and a path in a finite graph has length strictly less than , since its vertices are distinct. An induction along that path shows that its endpoint lies in the -th closure where is the path's length; because is inflationary the closures are nested increasing, so the endpoint also lies in the -th closure. Taking a path rather than an arbitrary walk is what makes the fixed iteration count 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 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 holds because the zeroth closure is .
import Definitions.Def_FastReachability
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