An edge-covering vertex set bounds the number of edges
ProvedArexychen.Erdos180.edgeCount_le_card_mul_degree_bound_of_edges_meet_finsetarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a simple graph on a finite vertex type, with decidable adjacency. Let be a finite set of vertices and let be a natural number. If every vertex in has degree at most , and every edge has at least one endpoint in , then
No degree restriction is imposed outside .
Preamble
import Definitions.Def_arexychen_erdos180_core import Mathlib.Analysis.Asymptotics.Theta import Mathlib.Combinatorics.SimpleGraph.Acyclic import Mathlib.Combinatorics.SimpleGraph.Basic import Mathlib.Combinatorics.SimpleGraph.Finite import Mathlib.Combinatorics.SimpleGraph.Maps import Mathlib.Combinatorics.SimpleGraph.Matching import Mathlib.Combinatorics.SimpleGraph.Subgraph import Mathlib.Tactic open Filter open Asymptotics attribute [local instance] SimpleGraph.neighborSetFintype universe u v w open Arexychen.Erdos180
Formal statement
theorem Arexychen.Erdos180.edgeCount_le_card_mul_degree_bound_of_edges_meet_finset
{V : Type u} [Fintype V]
(G : SimpleGraph V) [DecidableRel G.Adj]
(T : Finset V) (A : ℕ)
(hdeg : ∀ v ∈ T, G.degree v ≤ A)
(hcover : ∀ ⦃x y : V⦄, G.Adj x y → x ∈ T ∨ y ∈ T) :
edgeCount G ≤ T.card * A := by sorry
Source