simple_graph_card_low_left_degree_ge
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
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)|.
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)).
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
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).
uses
G.card_neighborFinset_eq_degree,SimpleGraph.mem_neighborFinset,lt_trichotomy,G.irrefl,card_union_of_disjoint,disjoint_filter,lt_irreflhave 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 _)
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.
uses
card_filter,Finset.sum_commhave hswap : ∑ v, ld v = ∑ v, rd v := by simp only [hld, hrd, card_filter] exact Finset.sum_comm
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)|.
uses
G.sum_degrees_eq_twice_card_edges,sum_add_distrib,sum_congrhave 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
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)|.
uses
card_filter_add_card_filter_not,card_univset 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]
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.
uses
card_nsmul_le_sum,not_lt,nsmul_eq_mul,sum_le_sum_of_subset_of_nonneg,subset_univ,Nat.cast_nonneg,Nat.cast_sumhave 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
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|.
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 : ℝ)
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.
uses
Nat.eq_zero_or_posrcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn · have : Lo.card = 0 := by omega rw [this, hn]; simp
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.
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.
- When |V(G)| = 0, division by |V(G)| in the average degree condition 2|E(G)|/|V(G)| ≤ k requires a separate edge-case check to clear denominators safely.
- The final algebraic inequality in step 9 is verified automatically by the nonlinear arithmetic decision procedure `nlinarith`, which algebraically combines the bounds on |Hi| and 2|E(G)| with the partition of |V(G)|.
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.
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