is_cograph
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
- cograph_is_distance_hereditaryEvery finite cograph is distance-hereditary.
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