Existence of a 1-Regular Spanning Subgraph in Finite Bridgeless Cubic Graphs
ProvedOPG37271.exists_one_regular_of_bridgeless_cubiccombinatoricsgraph-theorymatching
Every finite bridgeless -regular simple graph contains a -regular spanning subgraph (whose complement is a -factor).
Preamble
import Definitions.Def_opg37271_star_edge_coloring import Mathlib.Combinatorics.SimpleGraph.DeleteEdges universe u namespace OPG37271
Formal statement
theorem exists_one_regular_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 : SimpleGraph V, M ≤ G ∧ ∀ v : V, (M.neighborSet v).encard = 1 := by sorry
end OPG37271Source
Julius Petersen, Acta Mathematica 15 (1891), 193–220; used in Dvořák, Mohar, and Šámal (2013), Proof of Theorem 4.1(a).