ExampleConstruction: AI-adaptedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-26

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.

$P_{n}$ is prime for every $n \geq 4$

Example

For every integer $n \geq 4$ , the path $P_{n}$ is prime.

Facts & Assumptions

Given: An integer $n \geq 4$ and the path $P_{n}$ with vertices $0, 1, \dots, n - 1$ in order.

[L1]

A graph is prime when it has no nontrivial module (Prime graphs: those whose only modules are the trivial ones, Modules of a graph, and the trivial modules).

[L2]

In a connected graph, every nonempty proper module has some outside vertex complete to it (In a connected graph, some vertex outside a nonempty proper module is complete to it).

[L3]

In the path $P_{n}$ , every interior vertex has exactly two neighbours, namely the preceding and following vertices in the path order (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices, Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

Verification

technique · contradiction

1.1

Suppose, for contradiction, that $P_{n}$ has a nontrivial module $M$ . Then $M$ is a nonempty proper module, so [L2] gives a vertex $v \notin M$ complete to $M$ .

assume-contraL2

2.1

Since $v$ is complete to $M$ in a path, [L3] forces $v$ to be an interior vertex and $M$ to be exactly the two neighbours of $v$ .

step 1.1L3

3.1

One of the vertices at distance two from $v$ exists because $n \geq 4$ , and it is adjacent to exactly one of the two neighbours of $v$ . That vertex therefore splits $M$ , contradicting that $M$ is a module.

step 2.1given

4.1

No nontrivial module exists, so [L1] makes $P_{n}$ prime.

step 3.1L1discharge-contradiction∎

Depends on

Used by

An induced subgraph of a prime graph need not be prime Counterexample

Dependency tree · two levels

15 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

M. Habib and C. Paul, A Survey on Algorithmic Aspects of Modular Decomposition, sec. 2.4 (standard reference, not scraped)

PnPn​ is prime for every n≥4n≥4