Session-authored (Fable 5 assisted)

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.

✓ 5 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Cographs, Perfect Patterns and Pure Pairs - Examples

1 · Prerequisites

2 · Summary

These examples keep the page's finite witnesses explicit. They show a small cograph decomposition, a perfect graph that is not a cograph, equality in the additive $κ$ theorem, a perfect pattern that escapes the cograph class, and a concrete blockade-rainbow copy of $P_{4}$ .

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

The four-cycle is a cograph

Example

The four-cycle $C_{4}$ is a cograph.

Facts & Assumptions

Given: The cycle $C_{4}$ on vertices $0, 1, 2, 3$ .

[L1]

Any graph built from one-vertex graphs by repeated disjoint unions and complete connections is a cograph (Cographs by the singleton, disjoint-union, and complete-connection recursion).

[L2]

In $C_{4}$ , the edges are exactly $01, 12, 23, 30$ (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L3]

The complete connection of two vertex-disjoint graphs is obtained by keeping all internal edges and adding every possible cross edge (The complete connection of two disjoint graphs).

Verification

technique · direct construction

1.1

Let $A : = {0, 2}$ and $B : = {1, 3}$ . By [L2], there is no edge inside $A$ and no edge inside $B$ , while every cross pair $0$ - $1$ , $1$ - $2$ , $2$ - $3$ , and $3$ - $0$ is an edge. Thus the induced graphs on $A$ and $B$ are two edgeless two-vertex graphs.

2.1

Each edgeless two-vertex graph is a cograph, because it is the disjoint union of two one-vertex graphs. Step 1.1 and [L3] show that $C_{4}$ is the complete connection of those two cographs. Therefore [L1] makes $C_{4}$ a cograph.

step 1.1L1L3

3.1

Hence the four-cycle is a cograph.

step 2.1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

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∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-28Open item page →

A two-block pure blockade can realize equality in the additive kappa theorem

Example

Equality can occur in the additive $κ$ theorem for a two-block pure blockade.

Facts & Assumptions

Given: The complete graph $K_{5}$ on vertices $a_{1}, a_{2}, b_{1}, b_{2}, b_{3}$ , with blocks $A : = {a_{1}, a_{2}}$ and $B : = {b_{1}, b_{2}, b_{3}}$ .

[L1]

The pattern graph of a pure blockade records an edge exactly when the two corresponding blocks are complete (The pattern graph of a pure blockade).

[L2]

A clique on $m$ vertices has $ω = m$ , $α = 1$ , and therefore $κ = m$ (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ , The parameter kappa(G)=alpha(G)omega(G)).

[L3]

The additive $κ$ theorem states that a pure blockade with cograph pattern satisfies $κ (G [V (B)]) \geq \sum_{i} κ (G [B_{i}])$ (A pure blockade with a cograph pattern has additive kappa).

Verification

technique · direct computation

1.1

The blockade $(A, B)$ is pure, and the two blocks are complete to each other because the ambient graph is $K_{5}$ . Hence its pattern graph is $K_{2}$ , which is a cograph.

L1given

1.2

The induced subgraphs on $A$ , on $B$ , and on $A \cup B$ are respectively $K_{2}$ , $K_{3}$ , and $K_{5}$ . By [L2], $κ (G [A]) = 2, κ (G [B]) = 3, κ (G [A \cup B]) = 5.$ So $κ (G [A \cup B]) = κ (G [A]) + κ (G [B]) .$

2.1

Thus this two-block pure blockade attains equality in the inequality from [L3].

step 1.1step 1.2L3∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-28Open item page →

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

Example

A pure blockade may have a perfect pattern graph without having a cograph pattern graph.

Facts & Assumptions

Given: The path $P_{5}$ on vertices $0, 1, 2, 3, 4$ , and the singleton blocks $B_{i} : = {i - 1}$ for $1 \leq i \leq 5$ .

[L1]

The preceding example shows that $P_{5}$ is perfect but not a cograph (The five-vertex path is perfect but not a cograph).

[L2]

In the pattern graph of a pure blockade, two indices are adjacent exactly when the corresponding two blocks are complete (The pattern graph of a pure blockade).

[L3]

The graph $P_{5}$ has edges exactly $01, 12, 23, 34$ (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct construction

1.1

Because each block $B_{i}$ is a singleton, every pair $(B_{i}, B_{j})$ is either complete or anticomplete according to whether its two vertices are adjacent. Hence $(B_{1}, \dots, B_{5})$ is a pure blockade in the graph $P_{5}$ .

L3given

2.1

By [L2], the pattern graph has an edge $i j$ exactly when the vertices $i - 1$ and $j - 1$ are adjacent in $P_{5}$ . Therefore the pattern graph of $(B_{1}, \dots, B_{5})$ is itself $P_{5}$ .

step 1.1L2L3

3.1

Step 2.1 and [L1] show that this pure blockade has a perfect pattern that is not a cograph.

step 2.1L1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-28Open item page →

A four-block blockade-rainbow copy of P_4

Example

The path $P_{4}$ has a blockade-rainbow copy with four singleton blocks.

Facts & Assumptions

Given: The path $P_{4}$ on vertices $0, 1, 2, 3$ , with blocks $B_{1} : = {0}$ , $B_{2} : = {1}$ , $B_{3} : = {2}$ , and $B_{4} : = {3}$ .

[L1]

An induced subgraph is $B$ -rainbow when it lies in the support of the blockade and meets each block in at most one vertex (A blockade-rainbow induced copy).

[L2]

The graph $P_{4}$ has edges exactly $01, 12, 23$ (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L3]

The support of the blockade $(B_{1}, B_{2}, B_{3}, B_{4})$ is the union of those four singleton blocks (Blockades, their length, their width, and their support).

Verification

technique · direct construction

1.1

The support of the blockade is ${0, 1, 2, 3}$ by [L3], so the whole graph $P_{4}$ already lies inside that support.

L3given

2.1

Each block $B_{i}$ contains exactly one vertex of $P_{4}$ , so the induced copy of $P_{4}$ given by the whole graph meets each block in at most one vertex. By [L1], it is therefore blockade-rainbow.

step 1.1L1L2

3.1

Hence the path $P_{4}$ has a four-block blockade-rainbow copy.

step 2.1∎

Cographs, Perfect Patterns and Pure Pairs - Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The four-cycle is a cograph

Example

Facts & Assumptions

Verification

The five-vertex path is perfect but not a cograph

Example

Facts & Assumptions

Verification

A two-block pure blockade can realize equality in the additive kappa theorem

Example

Facts & Assumptions

Verification

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

Example

Facts & Assumptions

Verification

A four-block blockade-rainbow copy of P_4

Example

Facts & Assumptions

Verification

Sources