is_pk_free_of_card_lt
Any simple graph on fewer than k vertices is P_k-free, as an induced embedding requires an injection from Fin k into V.
Statement
theorem is_pk_free_of_card_lt {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) (h : Fintype.card V < k) : IsPkFree G k
- Source
- step towards p7_claw_free_dominating_pair_of_no_hole
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- IsPkFreeA simple graph G is P_k-free if it contains no induced subgraph isomorphic to the path on k vertices.
- Used by 1
- not_p7_claw_free_dominating_pair_of_no_holeThe statement
p7_claw_free_dominating_pair_of_no_holeis false: The statement is FALSE. A concrete counterexample is the net graph (a…
- not_p7_claw_free_dominating_pair_of_no_holeThe statement
The proof, explained
The proof proceeds by contradiction. If G were not P_k-free, it would contain an induced path on k vertices, providing an injective map from Fin k into the vertex set V. The existence of this injection implies k ≤ |V|, which contradicts the assumption that |V| < k.
Suppose for contradiction that G contains P_k as an induced subgraph, yielding an embedding f : P_k ↪g G.
By definition, a graph G is P_k-free (IsPkFree G k) if the path graph on k vertices is not an induced subgraph of G. Assuming the contrary gives an induced containment, which provides an induced embedding f from the path graph on k vertices (whose vertex type is Fin k) into G.
intro hc rcases hc with ⟨f⟩
k ≤ |V|
The embedding f is in particular injective on vertices. By Fintype.card_le_of_injective, an injection from Fin k into V implies |Fin k| ≤ |V|. Simplifying with Fintype.card_fin (which states |Fin k| = k) gives k ≤ |V|.
uses
Fintype.card_le_of_injective,Fintype.card_finhave h1 := Fintype.card_le_of_injective f f.injective simp only [Fintype.card_fin] at h1
A contradiction is reached. automation
The inequality k ≤ |V| contradicts the hypothesis |V| < k. The omega tactic closes the goal using linear integer arithmetic.
omega
Fintype.card_le_of_injective- An injective map from a finite type α to a finite type β implies |α| ≤ |β|.
Fintype.card_fin- The cardinality of Fin n is n.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A graph on fewer than k vertices cannot contain an induced P_k. -/theorem is_pk_free_of_card_lt {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) (h : Fintype.card V < k) : IsPkFree G k := by intro hc rcases hc with ⟨f⟩ have h1 := Fintype.card_le_of_injective f f.injective simp only [Fintype.card_fin] at h1 omega