IsPkFree
def
A simple graph G is P_k-free if it contains no induced subgraph isomorphic to the path on k vertices.
Statement
def IsPkFree {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
- Defined in
- arXiv:2610.20129 Sec. 1.1
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 3
- 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_is_pk_free_claw_free_hole_dominatingThe statement
is_pk_free_claw_free_hole_dominatingis false: The statement is false as written: it allows k = 4 and m = 3 (since k - 1 =… - is_pk_free_of_card_ltAny simple graph on fewer than k vertices is P_k-free, as an induced embedding requires an injection from Fin k into V.
- not_p7_claw_free_dominating_pair_of_no_holeThe statement
Read back from the Lean
Given an arbitrary type V, a simple graph G on V, and a natural number k, IsPkFree G k is the proposition that G does not contain the path graph on k vertices (SimpleGraph.pathGraph k) as an induced subgraph (that is, SimpleGraph.IsIndContained (SimpleGraph.pathGraph k) G is false).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A simple graph is P_k-free if it does not contain the path graph on k vertices as an induced subgraph. -/ def IsPkFree {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := ¬ SimpleGraph.IsIndContained (SimpleGraph.pathGraph k) G