AFTD Auto-Formalizing Theoretical Domains

is_cograph

def

A graph F is a cograph if it does not contain an induced path on four vertices (P₄).

Statement

def is_cograph {α : Type*} (F : SimpleGraph α) : Prop
Defined in
arXiv:2610.13820, Fact 4.4
Verified
26 Oct 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a simple graph $F$ on a type $\alpha$, is_cograph F asserts that there do not exist vertices $a, b, c, d : \alpha$ such that: 1. $a, b, c, d$ are pairwise distinct ($a \neq b$, $a \neq c$, $a \neq d$, $b \neq c$, $b \neq d$, and $c \neq d$); 2. $a$ is adjacent to $b$ ($F.\mathrm{Adj}\ a\ b$); 3. $b$ is adjacent to $c$ ($F.\mathrm{Adj}\ b\ c$); 4. $c$ is adjacent to $d$ ($F.\mathrm{Adj}\ c\ d$); 5. $a$ is not adjacent to $c$ ($\neg F.\mathrm{Adj}\ a\ c$); 6. $a$ is not adjacent to $d$ ($\neg F.\mathrm{Adj}\ a\ d$); and 7. $b$ is not adjacent to $d$ ($\neg F.\mathrm{Adj}\ b\ d$). (That is, $F$ does not contain an induced path on four vertices, $P_4$. Note that the definition shadow-binds the identifier $F$ from the knowledge base abbrev.)

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 graph is a cograph if it contains no induced path of four vertices. -/
def is_cograph {α : Type*} (F : SimpleGraph α) : Prop := ¬ ∃ (a b c d : α),
    a ≠ b ∧ a ≠ c ∧ a ≠ d ∧ b ≠ c ∧ b ≠ d ∧ c ≠ d ∧
    F.Adj a b ∧ F.Adj b c ∧ F.Adj c d ∧
    ¬ F.Adj a c ∧ ¬ F.Adj a d ∧ ¬ F.Adj b d
See it in the graphDiscuss this resultChallenge it