ExampleConstruction: AI-adaptedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (gpt-5.6-terra)audited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The five-vertex path is perfect but not a cograph

Example

The path $P_{5}$ is perfect but not a cograph.

Facts & Assumptions

Given: The path $P_{5}$ on vertices $0, 1, 2, 3, 4$ .

[L1]

A graph is perfect when every induced subgraph $H$ satisfies $χ (H) = ω (H)$ (Perfect graphs).

[L2]

The path $P_{5}$ has edges exactly $01, 12, 23, 34$ , so its first four vertices induce $P_{4}$ (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L3]

A graph is a cograph if and only if it is $P_{4}$ -free (The cographs are exactly the P_4-free graphs).

[F1]

Every induced subgraph of a path is a disjoint union of shorter paths, obtained by deleting vertices and keeping the remaining consecutive segments.

Verification

technique · direct finite check

1.1

Let $H$ be an induced subgraph of $P_{5}$ . By [F1], each connected component of $H$ is a path. Colour each component alternately along the path. This gives a proper colouring with $0$ colours when $H$ is empty, with $1$ colour when $H$ is nonempty and edgeless, and with $2$ colours when $H$ has an edge.

F1L2

1.2

By [L2], the vertices ${0, 1, 2, 3}$ induce $P_{4}$ . Therefore $P_{5}$ is not $P_{4}$ -free, and [L3] shows that $P_{5}$ is not a cograph.

L2L3

2.1

The same trichotomy gives the clique number of $H$ : it is $0$ when $H$ is empty, $1$ when $H$ is nonempty and edgeless, and $2$ when $H$ has an edge, because no path contains a triangle and disjoint union adds no new edges. Hence $χ (H) = ω (H)$ for every induced subgraph $H$ , so [L1] shows that $P_{5}$ is perfect.

step 1.1F1L1

3.1

Therefore $P_{5}$ is perfect but not a cograph.

step 2.1step 1.2∎

Depends on

Used by

A pure blockade can have a perfect pattern that is not a cograph Example

Dependency tree · two levels

21 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Maria Chudnovsky, The Erdos-Hajnal Conjecture - A Survey, Introduction (standard reference, not scraped)
Tero Harju, Lecture Notes on Combinatorial Structures in Graph Theory, Exercise 5.3 (standard reference, not scraped)