AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it