Lemma B.3 — the peeling procedure finds the largest induced subgraph with minimum degree above
ProvedLNTopology.Hermetic.lemma_B_3Let be a finite simple graph with vertex set , let be a real number, and let be the output of the peeling procedure of Lemma B.3, which repeatedly deletes every vertex having at most neighbours among the remaining vertices. Then
- every has more than neighbours in ; and
- every in which each vertex has more than neighbours in is contained in .
Consequently the procedure returns a nonempty induced subgraph with if one exists, and the empty graph otherwise. With this is the algorithm of Lemma B.3, which finds the subnetwork to which Lemma B.2 is applied.
Formalization Note The statement of Lemma B.3 promises a subgraph with , while the procedure of its proof deletes vertices of degree and therefore finds ; for integer the two differ (a -regular graph). The procedure as written in the proof is formalized; the proof of Theorem 3.8 needs only this strict version. The existence of "an algorithm" (trivial classically) and the running time are not formalized. The threshold is an arbitrary real .
import Mathlib import Definitions.Def_LNTopology_Hermetic_Peel
namespace LNTopology.Hermetic
/-- Lemma B.3, correctness of the peeling procedure of its proof: repeatedly deleting every vertex
with at most `t` neighbours among the remaining vertices yields a set in which every vertex has
more than `t` neighbours, and which contains every vertex set with that property. -/
theorem lemma_B_3 {W : Type*} [Fintype W] [DecidableEq W] (G : SimpleGraph W)
[DecidableRel G.Adj] (t : ℝ) :
(∀ v ∈ peel G t, t < ((G.neighborFinset v ∩ peel G t).card : ℝ)) ∧
∀ W' : Finset W, (∀ v ∈ W', t < ((G.neighborFinset v ∩ W').card : ℝ)) →
W' ⊆ peel G t := by sorry
end LNTopology.Hermetic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.