Lemma B.4 — a graph with average degree has a subgraph with
ProvedLNTopology.Hermetic.lemma_B_4Let be a finite simple graph with vertex set and let be a real number. If the average degree of is at least ,
then has a nonempty induced subgraph with minimum degree : there is a nonempty such that every has more than neighbours in .
This classical fact (Diestel, Graph Theory, Prop. 1.2.2) supplies the dense subnetwork to which Lemma B.2 is applied in the proof of Theorem 3.8.
Formalization Note "Average degree " is read as "at least ", as in the paper's proof ("the average degree is at least "); this implies the version with equality. The hypothesis is added: for an edgeless graph and no nonempty subgraph has minimum degree . Theorem 3.8 uses the lemma with . Nonemptiness of is part of the conclusion, as in the proof. Subgraphs are induced subgraphs, given by their vertex sets.
import Mathlib
namespace LNTopology.Hermetic
/-- Lemma B.4: a finite graph with average degree at least `2d`, `d > 0`, has a nonempty induced
subgraph of minimum degree greater than `d`. -/
theorem lemma_B_4 {W : Type*} [Fintype W] [DecidableEq W] (G : SimpleGraph W)
[DecidableRel G.Adj] (d : ℝ) (hd : 0 < d)
(havg : 2 * d ≤ (∑ v, (G.degree v : ℝ)) / (Fintype.card W : ℝ)) :
∃ W' : Finset W, W'.Nonempty ∧
∀ v ∈ W', d < ((G.neighborFinset v ∩ W').card : ℝ) := by sorry
end LNTopology.Hermetic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.