AFTD Auto-Formalizing Theoretical Domains

is_pk_free_of_card_lt

theoremverified

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

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.

  1. 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.

    lines 4–5

      intro hc
      rcases hc with ⟨f⟩
  2. 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|.

    lines 6–7

    uses Fintype.card_le_of_injective, Fintype.card_fin

      have h1 := Fintype.card_le_of_injective f f.injective
      simp only [Fintype.card_fin] at h1
  3. A contradiction is reached. automation

    The inequality k ≤ |V| contradicts the hypothesis |V| < k. The omega tactic closes the goal using linear integer arithmetic.

    line 8

      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

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