Embedding a canonical matching from a finite matching subgraph
ProvedArexychen.Erdos180.matching_embedding_of_edgeFinset_card_gearexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a matching subgraph of a simple graph on an arbitrary vertex type. Assume decidable adjacency for and a finite enumeration of its vertices. If the graph on those vertices has at least unordered edges, then the canonical -edge matching on embeds into by an injective edge-preserving map. The natural number may be zero, and the ambient vertex type need not be finite.
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 universe u v w open Arexychen.Erdos180
Formal statement
theorem Arexychen.Erdos180.matching_embedding_of_edgeFinset_card_ge
{V : Type u} {G : SimpleGraph V}
(M : G.Subgraph) (hM : M.IsMatching) [DecidableRel M.Adj] [Fintype M.verts]
{b : ℕ} (hcard : b ≤ M.coe.edgeFinset.card) :
EmbedsAsSubgraph (matchingGraph b) G := by sorry
Source