AFTD Auto-Formalizing Theoretical Domains

simple_graph_max_degree_deleteEdges_le

theoremverified

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.

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

    line 6

      intro v
  2. The 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).

    line 7

    uses le_trans, SimpleGraph.degree_le_of_le, SimpleGraph.deleteEdges_le

      exact 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

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