Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma B.4 — a graph with average degree 2d2d2d has a subgraph with δ(G′)>d\delta(G')>dδ(G′)>d

Proved
LNTopology.Hermetic.lemma_B_4

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

graph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let GGG be a finite simple graph with vertex set WWW and let d>0d>0d>0 be a real number. If the average degree of GGG is at least 2d2d2d,

1∣W∣∑v∈Wdeg⁡G(v) ≥ 2d,\frac{1}{|W|}\sum_{v\in W}\deg_G(v)\ \ge\ 2d,∣W∣1​v∈W∑​degG​(v) ≥ 2d,

then GGG has a nonempty induced subgraph G′G'G′ with minimum degree δ(G′)>d\delta(G')>dδ(G′)>d: there is a nonempty W′⊆WW'\subseteq WW′⊆W such that every v∈W′v\in W'v∈W′ has more than ddd neighbours in W′W'W′.

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 2d2d2d" is read as "at least 2d2d2d", as in the paper's proof ("the average degree is at least 2d2d2d"); this implies the version with equality. The hypothesis d>0d>0d>0 is added: for an edgeless graph and d=0d=0d=0 no nonempty subgraph has minimum degree >0>0>0. Theorem 3.8 uses the lemma with d=dˉ(G)/2>0d=\bar d(G)/2>0d=dˉ(G)/2>0. Nonemptiness of G′G'G′ is part of the conclusion, as in the proof. Subgraphs are induced subgraphs, given by their vertex sets.

Preamble
import Mathlib
Formal statement
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
Source
Guasoni, Huberman & Shikhelman, Lightning Network Economics: Topology, SSRN 4439190 (version of Feb. 3, 2023), p. 12 (PDF p. 13), Lemma B.4
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

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