Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A forbidden matching member gives a bounded edge-covering vertex set

Proved
Arexychen.Erdos180.familyFree_exists_edgeCover_card_le_two_mul_pred_card_of_matching

by arexychen · Sep 9, 2026 · Mathlib c5ea003 (Lean v4.30.0)

arexychen-erdos180-migrationerdos-180extremal-graph-theorygraph-theory

Let FFF be a finite indexed family of finite simple graphs, and let jjj be an index whose reduced graph is a matching with at least two edges. Every FFF-free graph GGG on Fin⁡(n)\operatorname{Fin}(n)Fin(n) has a vertex set TTT meeting every edge and satisfying

∣T∣≤2(∣V(Fj)∣−1).|T|\le 2\bigl(|V(F_j)|-1\bigr).∣T∣≤2(∣V(Fj​)∣−1).

The bound uses the whole vertex set of FjF_jFj​, including isolated vertices, and natural-number subtraction. An index jjj 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
https://github.com/arexychen/Erdos180/blob/2ea42256708d02f5de1541b42cfbc1e1c00c7d03/Erdos180/Families/Upper.lean#L169-L216

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me