AFTD Auto-Formalizing Theoretical Domains

has_mad_lt_exists_degree_le_two

theoremverified

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.

  1. 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.

    lines 5–9

    uses not_exists, not_and, not_le

      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
  2. 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.

    lines 10–25

    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_map

      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
  3. 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|.

    lines 26–31

    uses SimpleGraph.sum_degrees_eq_twice_card_edges, Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, smul_eq_mul

      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
  4. 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)|.

    lines 32–38

    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)
  5. 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.

    lines 39–41

      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.

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

/-- `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
See it in the graphDiscuss this resultChallenge it