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.

✓ 4 results · all verified · 4 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; all 4 also cleared it.

Iterative Sparsification and the Five-Vertex Path — Examples

1 · Prerequisites

2 · Summary

These examples isolate the finite witnesses behind the two iteration chains: complete versus anticomplete blockades, the upside-down comb obstruction, and the layout notion used in the local-to-global niceness theorem.

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-31Open item page →

Two large anticonnected components give a complete two-blockade

Example

If $G$ has two distinct anticonnected components $A$ and $B$ , each of size at least $w$ , then $(A, B)$ is a complete $(2, w)$ -blockade.

Facts & Assumptions

Given: Two distinct anticonnected components $A, B$ of a graph $G$ with $∣ A ∣, ∣ B ∣ \geq w > 0$ .

[L1]

Distinct anticonnected components are complete to one another (Distinct connected components are anticomplete, and distinct anticonnected components are complete).

Verification

technique · direct

1.1

The sets $A$ and $B$ are disjoint and nonempty because they are distinct components, and each has size at least $w$ by hypothesis.

given

2.1

By [L1], the pair $(A, B)$ is complete. Therefore $(A, B)$ is a complete $(2, w)$ -blockade.

step 1.1L1∎

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

A sparse $P_{5}$ -free graph with an anticomplete two-blockade

Example

Let $G$ be the disjoint union of two copies of $P_{3}$ . Then $G$ is $P_{5}$ -free and the two components form an anticomplete two-blockade.

Facts & Assumptions

Given: The graph $G = P_{3} ⊔ P_{3}$ with components $A$ and $B$ .

Verification

technique · direct finite check

1.1

The sets $A$ and $B$ are disjoint induced copies of $P_{3}$ , so they are anticomplete and each has size $3$ . Hence $(A, B)$ is an anticomplete $(2, 3)$ -blockade.

given

2.1

Every induced path in $G$ lies inside a single component, so it has at most three vertices. Thus $G$ is $P_{5}$ -free.

step 1.1∎

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

An upside-down comb with anticonnected blocks creates a $\overline{P_{5}}$

Example

In the mixed-pair obstruction from Claim 5.2.2 of the source, the five vertices $v, u, w, z, a_{i}$ induce $\overline{P_{5}}$ .

Facts & Assumptions

Given: Vertices $v, u, w, z, a_{i}$ such that $v u, v w, v z, u w, a_{i} w, a_{i} z \in E (G)$ and $v a_{i}, u a_{i}, u z, w z \notin E (G)$ .

Verification

technique · direct finite check

1.1

Among the five chosen vertices, the only nonedges are $v a_{i}$ , $a_{i} u$ , $u z$ , and $w z$ . All other pairs are adjacent by hypothesis.

given

2.1

The four nonedges from step 1.1 are exactly the edges of the path $v - a_{i} - u - z - w$ . Therefore the induced graph on ${v, u, w, z, a_{i}}$ is the complement of a five-vertex path.

step 1.1∎

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

A layout with a single wrong decided pair

Example

For this example, a layout consists of a pattern graph $J$ and pairwise disjoint vertex blocks $(A_{x} : x \in V (J))$ . Pairs inside one block are undecided. A pair with endpoints in distinct blocks $A_{x}, A_{y}$ is decided, with the pattern predicting an edge exactly when $x y \in E (J)$ ; the decided pair is wrong when its actual adjacency disagrees with that prediction.

Take such a layout whose pattern graph is a single edge $u v$ with blocks $A_{u} = {1, 2}$ and $A_{v} = {3, 4}$ . If the graph on ${1, 2, 3, 4}$ has all cross edges except $24$ , then the decided pair ${2, 4}$ is the unique wrong pair.

Facts & Assumptions

Given: The described two-block layout.

Verification

technique · direct finite check

1.1

The pairs inside $A_{u}$ and $A_{v}$ are undecided by definition of layout, so only cross-pairs are decided.

given

2.1

Because the pattern graph makes every cross-pair expected to be an edge, the missing edge $24$ is wrong, while all other cross-pairs agree with the pattern. Hence there is exactly one wrong decided pair.

step 1.1∎

Iterative Sparsification and the Five-Vertex Path — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Two large anticonnected components give a complete two-blockade

Example

Facts & Assumptions

Verification

A sparse P5P5​-free graph with an anticomplete two-blockade

Example

Facts & Assumptions

Verification

An upside-down comb with anticonnected blocks creates a P5‾P5​​

Example

Facts & Assumptions

Verification

A layout with a single wrong decided pair

Example

Facts & Assumptions

Verification

Sources

A sparse $P_{5}$ -free graph with an anticomplete two-blockade

An upside-down comb with anticonnected blocks creates a $\overline{P_{5}}$