has_mad_lt_exists_degree_le_two
If has_mad_lt G (7/3) holds, then every nonempty finite vertex set s contains a vertex with at most 2 neighbours in s.
Statement
theorem has_mad_lt_exists_degree_le_two {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hmad : has_mad_lt G (7 / 3)) : ∀ s : Finset V, s.Nonempty → ∃ v ∈ s, {w ∈ s | G.Adj v w}.card ≤ 2
- Source
- step towards sparse_strong_odd_five_list_coloring
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- has_mad_ltGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a rational number q, has_mad_lt G q…
The proof, explained
The theorem is proved by contradiction. If a nonempty vertex set s contains no vertex with at most 2 neighbours in s, then every vertex in the induced subgraph H = G[s] has degree at least 3. Summing degrees and applying the Handshaking Lemma gives 2|E(H)| ≥ 3|s|, which means the average degree of H is at least 3. This directly contradicts the assumption that the maximum average degree of G is strictly less than 7/3.
Assume for contradiction that no vertex in s has at most 2 neighbours in s, and instantiate the maximum average degree bound on the induced subgraph H = G[s].
We introduce the nonempty vertex subset s and assume for contradiction that every vertex in s has strictly more than 2 neighbours inside s. We also instantiate the hypothesis hmad on s to obtain that the average degree in the induced subgraph H = G[s] is strictly less than 7/3, that is, 2 * |E(H)| / |s| < 7/3.
uses
not_exists,not_and,not_leintro s hs by_contra hcon simp only [not_exists, not_and, not_le] at hcon have hm := hmad s hs set H := G.induce (s : Set V) with hH
Every vertex in the induced subgraph H has degree at least 3.
For an arbitrary vertex x ∈ s, we identify the neighbors of x in s with the neighbor finset of x in H via the subtype embedding. Since embeddings preserve cardinality, the degree of x in H equals the number of neighbors of x in s. By our contradiction assumption, this quantity is strictly greater than 2, so the degree is at least 3.
uses
SimpleGraph.card_neighborFinset_eq_degree,Function.Embedding.subtype,Finset.mem_filter,Finset.mem_map,SimpleGraph.mem_neighborFinset,Function.Embedding.coe_subtype,SimpleGraph.comap_adj,SimpleGraph.induce,Finset.card_maphave hdeg : ∀ x : (s : Set V), 3 ≤ H.degree x := by intro x have hx := hcon x.1 x.2 rw [← SimpleGraph.card_neighborFinset_eq_degree] have : ({w ∈ s | G.Adj x.1 w}) = (H.neighborFinset x).map (Function.Embedding.subtype _) := by ext w simp only [Finset.mem_filter, Finset.mem_map, SimpleGraph.mem_neighborFinset, Function.Embedding.coe_subtype, hH, SimpleGraph.comap_adj, SimpleGraph.induce, Function.Embedding.coe_subtype] constructor · rintro ⟨hw, hadj⟩ exact ⟨⟨w, hw⟩, hadj, rfl⟩ · rintro ⟨y, hy, rfl⟩ exact ⟨y.2, hy⟩ rw [this, Finset.card_map] at hx omega
The sum of degrees in H is at least 3 * |s|.
Summing the inequality deg_H(x) ≥ 3 over all vertices in H yields that the sum of degrees is bounded below by the sum of the constant 3 over the vertices of H. Identifying the number of vertices in H with |s|, this sum simplifies to 3 * |s|.
uses
SimpleGraph.sum_degrees_eq_twice_card_edges,Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,smul_eq_mulhave hsum := SimpleGraph.sum_degrees_eq_twice_card_edges H have hle : ∑ _x : (s : Set V), (3 : ℕ) ≤ ∑ x : (s : Set V), H.degree x := Finset.sum_le_sum fun x _ => hdeg x simp only [Finset.sum_const, Finset.card_univ, smul_eq_mul] at hle have hcard : Fintype.card (s : Set V) = s.card := by simp rw [hcard] at hle
The number of edges in H satisfies both 3 * |s| ≤ 2 * |E(H)| and 2 * |E(H)| < (7/3) * |s| in the rational numbers.
Since |s| > 0, clearing the denominator in 2 * |E(H)| / |s| < 7/3 gives 2 * |E(H)| < (7/3) * |s|. Meanwhile, by the Handshaking Lemma, the sum of degrees equals 2 * |E(H)|, so combining it with the sum-of-degrees lower bound gives 3 * |s| ≤ 2 * |E(H)|.
uses
div_lt_iff₀have hspos : (0 : ℚ) < s.card := by exact_mod_cast hs.card_pos rw [div_lt_iff₀ hspos] at hm have h2 : (3 * s.card : ℚ) ≤ 2 * (H.edgeFinset.card : ℚ) := by have : s.card * 3 ≤ 2 * H.edgeFinset.card := by have := hsum ▸ hle convert this using 2 exact_mod_cast (by omega : 3 * s.card ≤ 2 * H.edgeFinset.card)
A contradiction is obtained from 3 * |s| ≤ 2 * |E(H)| < (7/3) * |s|.
The two bounds imply 3 * |s| < (7/3) * |s|. Since |s| > 0, dividing by |s| would yield 3 < 7/3, which is false since 3 = 9/3. Linear arithmetic over the rationals closes the goal by contradiction.
have : (2 * (H.edgeFinset.card : ℚ)) = 2 * ((G.induce (s : Set V)).edgeFinset.card : ℚ) := by congr 2 linarith
not_exists- The negation of an existential quantifier ¬(∃ x, P x) is logically equivalent to the universal quantifier ∀ x, ¬(P x).
not_and- The negation of a conjunction ¬(a ∧ b) is logically equivalent to the implication a → ¬b.
not_le- In a linear order, ¬(a ≤ b) is logically equivalent to b < a.
SimpleGraph.card_neighborFinset_eq_degree- The degree of a vertex equals the cardinality of its neighbor finset.
Function.Embedding.subtype- The canonical embedding from a subtype {x // p x} into the ambient type.
Finset.mem_filter- An element belongs to a filtered finset filter p s if and only if it belongs to s and satisfies the predicate p.
Finset.mem_map- An element belongs to the image finset map f s if and only if it is the image under f of some element in s.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Function.Embedding.coe_subtype- The coercion of the canonical subtype embedding to a function is the subtype projection (Subtype.val).
SimpleGraph.comap_adj- In a comap graph, two vertices u and v are adjacent if and only if their images f(u) and f(v) are adjacent in the target graph.
SimpleGraph.induce- The induced subgraph on a subset of vertices, defined as the comap along the subtype inclusion.
Finset.card_map- An embedding preserves the cardinality of a finset under map.
SimpleGraph.sum_degrees_eq_twice_card_edges- The Handshaking Lemma: the sum of the degrees of all vertices in a finite graph equals twice the number of edges.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finset s, then the sum of f over s is at most the sum of g over s.
Finset.sum_const- The sum of a constant value b over a finset s equals |s| • b.
Finset.card_univ- The cardinality of the universal finset univ on a finite type equals Fintype.card of that type.
smul_eq_mul- Scalar multiplication of a type on itself coincides with ordinary multiplication.
div_lt_iff₀- For c > 0 in a linearly ordered field (or group with zero), b / c < a is equivalent to b < a * c.
- Lines 14–23 perform a subtype-to-ambient-type conversion via extensionality to show that the neighbors of x in the induced subgraph H correspond bijectively to the neighbors of x in s; this is standard formal bookkeeping that is taken for granted on paper.
- Line 30 is another bookkeeping step reconciling the cardinality of the subtype (s : Set V) with s.card.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- `mad < 7/3` forces 2-degeneracy: every nonempty vertex set contains a vertex with at most 2 neighbours inside it. -/theorem has_mad_lt_exists_degree_le_two {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hmad : has_mad_lt G (7 / 3)) : ∀ s : Finset V, s.Nonempty → ∃ v ∈ s, {w ∈ s | G.Adj v w}.card ≤ 2 := by intro s hs by_contra hcon simp only [not_exists, not_and, not_le] at hcon have hm := hmad s hs set H := G.induce (s : Set V) with hH have hdeg : ∀ x : (s : Set V), 3 ≤ H.degree x := by intro x have hx := hcon x.1 x.2 rw [← SimpleGraph.card_neighborFinset_eq_degree] have : ({w ∈ s | G.Adj x.1 w}) = (H.neighborFinset x).map (Function.Embedding.subtype _) := by ext w simp only [Finset.mem_filter, Finset.mem_map, SimpleGraph.mem_neighborFinset, Function.Embedding.coe_subtype, hH, SimpleGraph.comap_adj, SimpleGraph.induce, Function.Embedding.coe_subtype] constructor · rintro ⟨hw, hadj⟩ exact ⟨⟨w, hw⟩, hadj, rfl⟩ · rintro ⟨y, hy, rfl⟩ exact ⟨y.2, hy⟩ rw [this, Finset.card_map] at hx omega have hsum := SimpleGraph.sum_degrees_eq_twice_card_edges H have hle : ∑ _x : (s : Set V), (3 : ℕ) ≤ ∑ x : (s : Set V), H.degree x := Finset.sum_le_sum fun x _ => hdeg x simp only [Finset.sum_const, Finset.card_univ, smul_eq_mul] at hle have hcard : Fintype.card (s : Set V) = s.card := by simp rw [hcard] at hle have hspos : (0 : ℚ) < s.card := by exact_mod_cast hs.card_pos rw [div_lt_iff₀ hspos] at hm have h2 : (3 * s.card : ℚ) ≤ 2 * (H.edgeFinset.card : ℚ) := by have : s.card * 3 ≤ 2 * H.edgeFinset.card := by have := hsum ▸ hle convert this using 2 exact_mod_cast (by omega : 3 * s.card ≤ 2 * H.edgeFinset.card) have : (2 * (H.edgeFinset.card : ℚ)) = 2 * ((G.induce (s : Set V)).edgeFinset.card : ℚ) := by congr 2 linarith