CounterexampleConstruction: AI-generatedVerification: 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.

An induced subgraph of a prime graph need not be prime

Statement refuted

Every induced subgraph of a prime graph is prime.

Facts & Assumptions

Given: The five-vertex path $P_{5}$ with vertices $0, 1, 2, 3, 4$ in order.

[L1]

The path $P_{n}$ is prime for every $n \geq 4$ ( $P_{n}$ is prime for every $n \geq 4$ , Prime graphs: those whose only modules are the trivial ones).

[L2]

A graph with a proper module of size two is not prime (Modules of a graph, and the trivial modules, Prime graphs: those whose only modules are the trivial ones).

Counterexample

technique · constructive

1.1

By [L1], the graph $P_{5}$ is prime.

L1construct

1.2

Deleting the middle vertex $2$ leaves the induced subgraph on ${0, 1, 3, 4}$ , which is the disjoint union of the two edges $01$ and $34$ .

givenconstruct

2.1

In that four-vertex induced subgraph, the set ${0, 1}$ is a proper module of size two, since every outside vertex is anticomplete to it. So [L2] shows that the induced subgraph is not prime.

step 1.2L2

3.1

Hence a prime graph can have an induced subgraph that is not prime.

step 1.1step 2.1discharge-construct∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

14 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.