Deleting a vertex `u` drops the degree of each of its neighbours by at least one.
ProvedTriangularForest.degree_induce_compl_singleton_add_one_leaether-cataloglogic
Deleting a vertex u drops the degree of each of its neighbours by at least one.
theorem TriangularForest.degree_induce_compl_singleton_add_one_le[Fintype V] [DecidableEq V]
[DecidableRel G.Adj] {u v : V} (h : G.Adj v u) (hv : v ∈ ({u}ᶜ : Set V)) :
(G.induce ({u}ᶜ : Set V)).degree ⟨v, hv⟩ + 1 ≤ G.degree v := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Logic/TriangularForest/SharpBound.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Logic/TriangularForest/SharpBound.lean
import Mathlib
import Definitions.Def_Logic_TriangularForest_Decomposition
/-!
# The sharp sparsity bound for triangular forests
A connected triangular forest on `n` vertices with `t` triangular blocks has `n - 1 + t` edges
and `2t ≤ n - 1`, so `2e ≤ 3(n-1)`. Here we prove this sharp bound
(`TriangularForest.two_mul_card_edgeFinset_le`) without developing block decompositions, by
refining the longest-path argument of `Logic.TriangularForest.Sparsity`:
* `TriangularForest.degree_second_le_two` — if `p = a → v₁ → v₂ → ⋯` is a longest path in a
triangular forest and `a` is also adjacent to `v₂` (which happens as soon as `a` has degree
two), then the *second* vertex `v₁` also has degree at most two. Neighbours of `v₁` off the
path would allow the reroute `y → v₁ → a → v₂ → ⋯`, which is longer; neighbours further along
the path close a cycle of length `≥ 4`, except for the vertex `v₃`, which is excluded by the
4-cycle `a → v₁ → v₃ → v₂ → a`.
* `TriangularForest.exists_adj_degree_le_two` — hence a triangular forest of minimum degree at
least two contains an *edge* both of whose endpoints have degree two (a leaf triangle).
* Deleting such a pair removes two vertices and exactly three edges, which powers the induction
giving `2e ≤ 3(n-1)`.
As a consequence `Kₙ` fails to decompose into two triangular forests already for `n ≥ 6`, which
combined with `TriangularForest.completeGraph_decomposesIntoTwo_five` pins the threshold
exactly: `Kₙ` decomposes into two triangular forests if and only if `n ≤ 5`.
-/
open TriangularForest
open SimpleGraph Finset
variable {V : Type*} {G : SimpleGraph V}
variable [Fintype V] [DecidableEq V] [DecidableRel G.Adj]Formal statement
theorem TriangularForest.degree_induce_compl_singleton_add_one_le[Fintype V] [DecidableEq V]
[DecidableRel G.Adj] {u v : V} (h : G.Adj v u) (hv : v ∈ ({u}ᶜ : Set V)) :
(G.induce ({u}ᶜ : Set V)).degree ⟨v, hv⟩ + 1 ≤ G.degree v := by sorrySource