Embedding a graph with matching reduction into a canonical matching
ProvedArexychen.Erdos180.embeds_into_large_matchingGraph_of_isMatching_deleteIsolatedarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a simple graph on a finite vertex type . If, after deleting isolated vertices, each vertex has at most one neighbor, then the whole embeds as an ordinary subgraph into the canonical matching with edges. The target has vertex type ; isolated vertices of are retained.
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.embeds_into_large_matchingGraph_of_isMatching_deleteIsolated
{α : Type u} [Fintype α] (H : SimpleGraph α)
(hmatch : IsMatchingGraph (deleteIsolated H)) :
EmbedsAsSubgraph H (matchingGraph (Fintype.card α)) := by sorry
Source