simple_graph_max_degree_deleteEdges_le
Deleting edges preserves maximum degree bounds: if every vertex has degree at most d, then deleting any set of edges preserves this bound.
Statement
theorem simple_graph_max_degree_deleteEdges_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s : Set (Sym2 V)) [DecidablePred (· ∈ s)] (d : ℕ) (h : ∀ v, G.degree v ≤ d) : ∀ v, (G.deleteEdges s).degree v ≤ d
- Source
- step towards simple_graph_triangle_cover_number_le_two_mul_packing_number_of_max_degree_le_eleven
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To bound the degree of an arbitrary vertex after deleting edges, the proof observes that edge deletion produces a subgraph. Consequently, the degree of any vertex in the modified graph is at most its degree in the original graph, which is bounded by d by hypothesis. The result follows by transitivity of inequality.
It suffices to verify the degree bound for an arbitrary vertex v.
We introduce an arbitrary vertex v of V to prove the universal statement.
intro vThe degree of v after deleting the edge set s is at most d.
Deleting edges from G yields a subgraph (SimpleGraph.deleteEdges_le), so the degree of v cannot increase (SimpleGraph.degree_le_of_le). Since the degree of v in G is at most d by hypothesis h, the bound holds by transitivity of ≤ (le_trans).
uses
le_trans,SimpleGraph.degree_le_of_le,SimpleGraph.deleteEdges_leexact le_trans (SimpleGraph.degree_le_of_le (SimpleGraph.deleteEdges_le s)) (h v)
le_trans- If a ≤ b and b ≤ c, then a ≤ c (transitivity of inequality).
SimpleGraph.degree_le_of_le- If a graph G is a subgraph of H (G ≤ H), then the degree of any vertex in G is at most its degree in H.
SimpleGraph.deleteEdges_le- The graph obtained by deleting a set of edges s from G is a subgraph of G (G \\ s ≤ 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.
/-- Deleting edges preserves maximum degree bounds: if every vertex has degree at most d, then deleting any set of edges preserves this bound. -/theorem simple_graph_max_degree_deleteEdges_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (s : Set (Sym2 V)) [DecidablePred (· ∈ s)] (d : ℕ) (h : ∀ v, G.degree v ≤ d) : ∀ v, (G.deleteEdges s).degree v ≤ d := by intro v exact le_trans (SimpleGraph.degree_le_of_le (SimpleGraph.deleteEdges_le s)) (h v)