AFTD Auto-Formalizing Theoretical Domains

simple_graph_card_low_left_degree_ge

theoremverifiedformalization

Let G be a finite graph, k a real with k ≥ 2|E(G)|/|V(G)|, and 0 ≤ q < k. For any ordering σ of the vertices, at least (q/(k+q))·|V(G)| vertices have fewer than (k+q)/2 neighbours before them in σ.

Statement

theorem simple_graph_card_low_left_degree_ge {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (σ : V ≃ Fin (Fintype.card V)) (k q : ℝ)
    (hk : 2 * (G.edgeFinset.card : ℝ) / Fintype.card V ≤ k) (hq : 0 ≤ q) (hqk : q < k) :
    q / (k + q) * Fintype.card V ≤
      ((Finset.univ.filter (fun v =>
        (((Finset.univ.filter (fun u => G.Adj u v ∧ σ u < σ v)).card : ℝ) < (k + q) / 2))).card : ℝ)
Formalizes
arXiv:2610.14374 (Greedy coloring and simple exponential strengthenings of Brooks' theorem), Lemma 5.
Verified
14 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The proof partitions the vertices into those with low left-degree Lo = {v | ld(v) < (k+q)/2} and high left-degree Hi = {v | ld(v) ≥ (k+q)/2}. Since every edge joins a vertex to one ordered after it, the sum of all left-degrees equals the total number of edges |E(G)|. This gives the upper bound |Hi| · (k+q)/2 ≤ ∑_{v ∈ Hi} ld(v) ≤ |E(G)|. Combining this bound with the average degree hypothesis 2|E(G)| ≤ k|V(G)| and the partition |V(G)| = |Lo| + |Hi| yields |Lo| ≥ (q/(k+q)) · |V(G)|.

  1. Define the left-degree ld(v) and right-degree rd(v) for each vertex v.

    For each vertex v, its left-degree ld(v) is defined as the number of neighbors u appearing before v in the ordering σ (that is, σ(u) < σ(v)), and its right-degree rd(v) is defined as the number of neighbors u appearing after v in σ (σ(v) < σ(u)).

    lines 7–8

      set ld : V → ℕ := fun v => (univ.filter (fun u => G.Adj u v ∧ σ u < σ v)).card with hld
      set rd : V → ℕ := fun v => (univ.filter (fun u => G.Adj v u ∧ σ v < σ u)).card with hrd
  2. For every vertex v, its degree equals the sum of its left-degree and right-degree: ld(v) + rd(v) = deg(v).

    The neighborhood of v is partitioned into neighbors ordered before v and neighbors ordered after v. By trichotomy of the ordering σ, any neighbor u of v satisfies σ(u) < σ(v) or σ(v) < σ(u), since σ(u) = σ(v) would imply u = v, which contradicts the fact that G has no self-loops (G.irrefl). Moreover, these two sets are disjoint because no element can satisfy both σ(u) < σ(v) and σ(v) < σ(u). Therefore, the degree of v, which is the cardinality of its neighborhood, is ld(v) + rd(v).

    lines 9–28

    uses G.card_neighborFinset_eq_degree, SimpleGraph.mem_neighborFinset, lt_trichotomy, G.irrefl, card_union_of_disjoint, disjoint_filter, lt_irrefl

      have hsplit : ∀ v, ld v + rd v = G.degree v := by
        intro v
        rw [← G.card_neighborFinset_eq_degree]
        have h : G.neighborFinset v = (univ.filter (fun u => G.Adj u v ∧ σ u < σ v)) ∪
            (univ.filter (fun u => G.Adj v u ∧ σ v < σ u)) := by
          ext u
          simp only [SimpleGraph.mem_neighborFinset, mem_union, mem_filter, mem_univ, true_and]
          constructor
          · intro h
            rcases lt_trichotomy (σ u) (σ v) with h1 | h1 | h1
            · exact Or.inl ⟨h.symm, h1⟩
            · exact absurd (σ.injective h1 ▸ h) G.irrefl
            · exact Or.inr ⟨h, h1⟩
          · rintro (⟨h, _⟩ | ⟨h, _⟩)
            · exact h.symm
            · exact h
        rw [h, card_union_of_disjoint]
        rw [disjoint_filter]
        intro u _ h1 h2
        exact absurd (h1.2.trans h2.2) (lt_irrefl _)
  3. The sum of left-degrees over all vertices equals the sum of right-degrees: ∑_{v} ld(v) = ∑_{v} rd(v).

    Rewriting the cardinalities ld(v) and rd(v) as sums of indicator functions over the vertex set, exchanging the two summation variables u and v via Finset.sum_comm swaps the roles of left- and right-neighbors, showing that the two total sums are identical.

    lines 29–31

    uses card_filter, Finset.sum_comm

      have hswap : ∑ v, ld v = ∑ v, rd v := by
        simp only [hld, hrd, card_filter]
        exact Finset.sum_comm
  4. The total sum of all left-degrees equals the number of edges: ∑_{v} ld(v) = |E(G)|. automation

    By Euler's handshaking lemma, the sum of all degrees is 2|E(G)|. Since deg(v) = ld(v) + rd(v) for every vertex and ∑ ld(v) = ∑ rd(v), the sum of degrees is 2 ∑ ld(v). Linear integer arithmetic (`omega`) deduces from 2 ∑ ld(v) = 2|E(G)| that ∑_{v} ld(v) = |E(G)|.

    lines 32–37

    uses G.sum_degrees_eq_twice_card_edges, sum_add_distrib, sum_congr

      have hE : ∑ v, ld v = G.edgeFinset.card := by
        have h2 := G.sum_degrees_eq_twice_card_edges
        have : ∑ v, G.degree v = ∑ v, ld v + ∑ v, rd v := by
          rw [← sum_add_distrib]
          exact sum_congr rfl (fun v _ => (hsplit v).symm)
        omega
  5. The vertices partition into low left-degree vertices Lo and high left-degree vertices Hi, with |Lo| + |Hi| = |V(G)|.

    Let Lo be the subset of vertices with left-degree strictly less than (k+q)/2, and Hi be the complement, vertices with left-degree at least (k+q)/2. Since Hi is the complement of Lo in the full vertex set, their cardinalities sum to the total number of vertices |V(G)|.

    lines 38–40

    uses card_filter_add_card_filter_not, card_univ

      set Lo := univ.filter (fun v => (ld v : ℝ) < (k + q) / 2) with hLo
      set Hi := univ.filter (fun v => ¬ (ld v : ℝ) < (k + q) / 2) with hHi
      have hcard : Lo.card + Hi.card = Fintype.card V := by rw [card_filter_add_card_filter_not, card_univ]
  6. The number of high left-degree vertices satisfies |Hi| · (k+q)/2 ≤ |E(G)|. automation

    Every vertex in Hi has left-degree at least (k+q)/2, so |Hi| · (k+q)/2 ≤ ∑_{v ∈ Hi} ld(v). Because left-degrees are nonnegative, the sum over the subset Hi is at most the total sum ∑_{v ∈ V} ld(v) = |E(G)|. Combining these inequalities via linear arithmetic (`linarith`) yields the bound.

    lines 41–52

    uses card_nsmul_le_sum, not_lt, nsmul_eq_mul, sum_le_sum_of_subset_of_nonneg, subset_univ, Nat.cast_nonneg, Nat.cast_sum

      have hHi_le : (Hi.card : ℝ) * ((k + q) / 2) ≤ G.edgeFinset.card := by
        have h1 : Hi.card • ((k + q) / 2) ≤ ∑ v ∈ Hi, (ld v : ℝ) := by
          apply card_nsmul_le_sum
          intro v hv
          simp only [hHi, mem_filter, mem_univ, true_and, not_lt] at hv
          exact hv
        rw [nsmul_eq_mul] at h1
        have h2 : ∑ v ∈ Hi, (ld v : ℝ) ≤ ∑ v, (ld v : ℝ) :=
          sum_le_sum_of_subset_of_nonneg (subset_univ _) (fun _ _ _ => Nat.cast_nonneg _)
        have h3 : ∑ v, (ld v : ℝ) = G.edgeFinset.card := by
          rw [← Nat.cast_sum, hE]
        linarith
  7. k + q > 0, the cardinality relation |Lo| + |Hi| = |V(G)| holds in ℝ, and the goal reduces to showing (q/(k+q)) · |V(G)| ≤ |Lo|.

    From 0 ≤ q and q < k, linear arithmetic gives k + q > 0. The integer partition equality |Lo| + |Hi| = |V(G)| is cast to the real numbers, and the target inequality is restated directly in terms of |Lo|.

    lines 53–55

      have hkq : 0 < k + q := by linarith
      have hcardR : (Lo.card : ℝ) + Hi.card = Fintype.card V := by exact_mod_cast hcard
      show q / (k + q) * Fintype.card V ≤ (Lo.card : ℝ)
  8. If |V(G)| = 0, the inequality holds trivially. automation

    When |V(G)| = 0, |Lo| must also be 0 because |Lo| ≤ |V(G)|. Substituting 0 for |V(G)| and |Lo| reduces both sides of the inequality to 0, which is closed immediately by simplification.

    lines 56–58

    uses Nat.eq_zero_or_pos

      rcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn
      · have : Lo.card = 0 := by omega
        rw [this, hn]; simp
  9. If |V(G)| > 0, the inequality (q/(k+q)) · |V(G)| ≤ |Lo| holds. automation

    When |V(G)| > 0, clearing denominators in the assumption 2|E(G)|/|V(G)| ≤ k gives 2|E(G)| ≤ k|V(G)|. The target inequality (q/(k+q)) · |V(G)| ≤ |Lo| is equivalent to q|V(G)| ≤ |Lo|(k+q). Substituting |Lo| = |V(G)| - |Hi|, this simplifies to |Hi|(k+q) ≤ k|V(G)|, which in turn is equivalent to |Hi| · (k+q)/2 ≤ k|V(G)|/2. Since |Hi| · (k+q)/2 ≤ |E(G)| ≤ k|V(G)|/2, the inequality holds; the nonlinear real arithmetic tactic `nlinarith` combines these bounds to close the goal.

    lines 59–63

    uses div_le_iff₀, div_mul_eq_mul_div

      · have hnR : (0 : ℝ) < Fintype.card V := by exact_mod_cast hn
        have hE2 : 2 * (G.edgeFinset.card : ℝ) ≤ k * Fintype.card V := by
          rwa [div_le_iff₀ hnR] at hk
        rw [div_mul_eq_mul_div, div_le_iff₀ hkq]
        nlinarith
G.card_neighborFinset_eq_degree
The number of neighbors of a vertex v equals the degree of v in the graph.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
lt_trichotomy
In any linear order, for any two elements a and b, exactly one of a < b, a = b, or b < a holds.
G.irrefl
In a simple graph, no vertex is adjacent to itself (there are no self-loops).
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
disjoint_filter
Two filtered subsets of a finite set are disjoint if and only if no element satisfies both filtering predicates.
lt_irrefl
Strict inequality is irreflexive: no element is strictly less than itself.
card_filter
The cardinality of a filtered subset equals the sum over the set of the indicator function of the predicate.
Finset.sum_comm
The order of summation in a finite double sum can be interchanged.
G.sum_degrees_eq_twice_card_edges
The sum of the degrees of all vertices in a finite graph equals twice the number of edges (Euler's handshaking lemma).
sum_add_distrib
A sum of a pointwise sum of two functions over a finite set equals the sum of the individual sums.
sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at every element.
card_filter_add_card_filter_not
For any predicate p on a finite set s, the number of elements satisfying p plus the number of elements not satisfying p equals |s|.
card_univ
The cardinality of the universal finset on α is the cardinality of the finite type α.
card_nsmul_le_sum
If every element of a finite set s has value at least c, then |s| · c is at most the sum of the values over s.
not_lt
In a linear order, ¬(a < b) is equivalent to b ≤ a.
nsmul_eq_mul
Scalar multiplication of a ring element by a natural number n equals multiplication by n cast to the ring.
sum_le_sum_of_subset_of_nonneg
The sum of a nonnegative function over a subset of a finite set is at most the sum over the full set.
subset_univ
Every finite subset of a finite type is contained in the universal finset.
Nat.cast_nonneg
The cast of any natural number into an ordered semiring is nonnegative.
Nat.cast_sum
The cast of a finite sum of natural numbers equals the sum of the casts.
Nat.eq_zero_or_pos
Every natural number is either 0 or strictly positive.
div_le_iff₀
For a positive real c, b / c ≤ a if and only if b ≤ a · c.
div_mul_eq_mul_div
Multiplying a quotient a / b by c is equal to (a · c) / b.

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

theorem simple_graph_card_low_left_degree_ge {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (σ : V ≃ Fin (Fintype.card V)) (k q : ℝ)    (hk : 2 * (G.edgeFinset.card : ℝ) / Fintype.card V ≤ k) (hq : 0 ≤ q) (hqk : q < k) :    q / (k + q) * Fintype.card V ≤      ((Finset.univ.filter (fun v =>        (((Finset.univ.filter (fun u => G.Adj u v ∧ σ u < σ v)).card : ℝ) < (k + q) / 2))).card : ℝ) := open Finset in by  set ld : V → ℕ := fun v => (univ.filter (fun u => G.Adj u v ∧ σ u < σ v)).card with hld  set rd : V → ℕ := fun v => (univ.filter (fun u => G.Adj v u ∧ σ v < σ u)).card with hrd  have hsplit : ∀ v, ld v + rd v = G.degree v := by    intro v    rw [← G.card_neighborFinset_eq_degree]    have h : G.neighborFinset v = (univ.filter (fun u => G.Adj u v ∧ σ u < σ v)) ∪        (univ.filter (fun u => G.Adj v u ∧ σ v < σ u)) := by      ext u      simp only [SimpleGraph.mem_neighborFinset, mem_union, mem_filter, mem_univ, true_and]      constructor      · intro h        rcases lt_trichotomy (σ u) (σ v) with h1 | h1 | h1        · exact Or.inl ⟨h.symm, h1⟩        · exact absurd (σ.injective h1 ▸ h) G.irrefl        · exact Or.inr ⟨h, h1⟩      · rintro (⟨h, _⟩ | ⟨h, _⟩)        · exact h.symm        · exact h    rw [h, card_union_of_disjoint]    rw [disjoint_filter]    intro u _ h1 h2    exact absurd (h1.2.trans h2.2) (lt_irrefl _)  have hswap : ∑ v, ld v = ∑ v, rd v := by    simp only [hld, hrd, card_filter]    exact Finset.sum_comm  have hE : ∑ v, ld v = G.edgeFinset.card := by    have h2 := G.sum_degrees_eq_twice_card_edges    have : ∑ v, G.degree v = ∑ v, ld v + ∑ v, rd v := by      rw [← sum_add_distrib]      exact sum_congr rfl (fun v _ => (hsplit v).symm)    omega  set Lo := univ.filter (fun v => (ld v : ℝ) < (k + q) / 2) with hLo  set Hi := univ.filter (fun v => ¬ (ld v : ℝ) < (k + q) / 2) with hHi  have hcard : Lo.card + Hi.card = Fintype.card V := by rw [card_filter_add_card_filter_not, card_univ]  have hHi_le : (Hi.card : ℝ) * ((k + q) / 2) ≤ G.edgeFinset.card := by    have h1 : Hi.card • ((k + q) / 2) ≤ ∑ v ∈ Hi, (ld v : ℝ) := by      apply card_nsmul_le_sum      intro v hv      simp only [hHi, mem_filter, mem_univ, true_and, not_lt] at hv      exact hv    rw [nsmul_eq_mul] at h1    have h2 : ∑ v ∈ Hi, (ld v : ℝ) ≤ ∑ v, (ld v : ℝ) :=      sum_le_sum_of_subset_of_nonneg (subset_univ _) (fun _ _ _ => Nat.cast_nonneg _)    have h3 : ∑ v, (ld v : ℝ) = G.edgeFinset.card := by      rw [← Nat.cast_sum, hE]    linarith  have hkq : 0 < k + q := by linarith  have hcardR : (Lo.card : ℝ) + Hi.card = Fintype.card V := by exact_mod_cast hcard  show q / (k + q) * Fintype.card V ≤ (Lo.card : ℝ)  rcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn  · have : Lo.card = 0 := by omega    rw [this, hn]; simp  · have hnR : (0 : ℝ) < Fintype.card V := by exact_mod_cast hn    have hE2 : 2 * (G.edgeFinset.card : ℝ) ≤ k * Fintype.card V := by      rwa [div_le_iff₀ hnR] at hk    rw [div_mul_eq_mul_div, div_le_iff₀ hkq]    nlinarith
See it in the graphDiscuss this resultChallenge it