Petersen's Theorem (1891): Every Finite Bridgeless Cubic Graph Has a Perfect Matching
ProvedPetersen.exists_isPerfectMatching_of_bridgeless_cubiccombinatoricsgraph-theorymatchingpetersen-theorem
Petersen's Theorem (1891). Every finite bridgeless -regular (cubic) simple graph admits a perfect matching.
Preamble
import Mathlib.Combinatorics.SimpleGraph.DeleteEdges import Mathlib.Combinatorics.SimpleGraph.Tutte universe u namespace Petersen
Formal statement
theorem exists_isPerfectMatching_of_bridgeless_cubic
{V : Type u} [Fintype V] (G : SimpleGraph V)
(hcubic : ∀ v : V, (G.neighborSet v).encard = 3)
(hbridgeless : ∀ u v : V, G.Adj u v → (G.deleteEdges {s(u, v)}).Reachable u v) :
∃ M : G.Subgraph, M.IsPerfectMatching := by sorry
end PetersenSource
Julius Petersen, Die Theorie der regulären graphs, Acta Mathematica 15 (1891), 193–220.