A forbidden matching member gives a bounded edge-covering vertex set
ProvedArexychen.Erdos180.familyFree_exists_edgeCover_card_le_two_mul_pred_card_of_matchingarexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory
Let be a finite indexed family of finite simple graphs, and let be an index whose reduced graph is a matching with at least two edges. Every -free graph on has a vertex set meeting every edge and satisfying
The bound uses the whole vertex set of , including isolated vertices, and natural-number subtraction. An index is supplied; there is no separate nonempty-typeclass binder.
Preamble
import Definitions.Def_arexychen_erdos180_families_bounds import Definitions.Def_arexychen_erdos180_finite 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.familyFree_exists_edgeCover_card_le_two_mul_pred_card_of_matching
{ι : Type v} [Finite ι] {F : ι → FiniteSimpleGraph.{u}}
{j : ι}
(hmatching : (F j).matchingWithAtLeastTwoEdgesAfterDeletingIsolated)
{n : ℕ} (G : SimpleGraph (Fin n))
(hfree : FamilyFree F G) :
∃ T : Finset (Fin n),
T.card ≤ 2 * (Fintype.card (F j).V - 1) ∧
∀ ⦃x y : Fin n⦄, G.Adj x y → x ∈ T ∨ y ∈ T := by sorry
Source