A maximal matching supplies an edge-covering vertex set
ProvedArexychen.Erdos180.exists_maximalMatching_edgeCoverarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Every simple graph on , for any natural , has a matching subgraph maximal among matching subgraphs under inclusion, whose vertex set meets every edge of . The statement requires no supplied decision procedure for adjacency and includes the empty host graph.
Preamble
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 universe u v w
Formal statement
theorem Arexychen.Erdos180.exists_maximalMatching_edgeCover
{n : ℕ} (G : SimpleGraph (Fin n)) :
∃ M : G.Subgraph,
M.IsMatching ∧
Maximal (fun N : G.Subgraph => N.IsMatching) M ∧
∀ ⦃x y : Fin n⦄, G.Adj x y → x ∈ M.verts ∨ y ∈ M.verts := by sorry
Source