TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 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.

Every prime graph on at least four vertices contains an induced P_4

Statement

If $G$ is a prime graph with at least four vertices, then $G$ contains an induced copy of $P_{4}$ .

Facts & Assumptions

Given: A prime graph $G$ with $∣ V (G) ∣ \geq 4$ .

[L1]

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

[L2]

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

[L3]

Every nontrivial cograph is disconnected or has disconnected complement (Every nontrivial cograph is disconnected or has disconnected complement).

[L4]

Every union of connected components is a module, and so is every union of anticomponents (Every union of connected components is a module, and so is every union of anticonnected components).

[F1]

If a partition of a set with at least four elements has at least two nonempty parts, then some proper union of its parts has cardinality between $2$ and $∣ V (G) ∣ - 1$ : either one part already has at least two elements, or else all parts are singletons and the union of two of them does.

Proof

technique · direct

1.1L2L3givenassume-contra

Suppose for contradiction that $G$ contains no induced $P_{4}$ . Then [L2] shows that $G$ is a cograph. Since $∣ V (G) ∣ \geq 4$ , the graph is nontrivial, so [L3] gives that $G$ is disconnected or $\overline{G}$ is disconnected.

2.1step 1.1L1L4F1discharge-contradiction

If $G$ is disconnected, its connected components form a partition of $V (G)$ into at least two nonempty parts. By [F1], choose a proper union $M$ of component vertex sets with $2 \leq ∣ M ∣ \leq ∣ V (G) ∣ - 1$ . Then [L4] makes $M$ a module of $G$ , and the cardinality bounds say that it is nontrivial. This contradicts [L1].

2.2step 1.1L1L4F1discharge-contradiction

If $\overline{G}$ is disconnected, then the anticomponents of $G$ form a partition of $V (G)$ into at least two nonempty parts. Again [F1] gives a proper union $M$ of anticomponent vertex sets with $2 \leq ∣ M ∣ \leq ∣ V (G) ∣ - 1$ , and [L4] makes $M$ a nontrivial module of $G$ , contradicting [L1].

3.1step 2.1step 2.2∎

Both alternatives from step 1.1 are impossible, so the assumption was false. Therefore $G$ contains an induced copy of $P_{4}$ .

Depends on

Used by

Dependency tree · two levels

25 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

Tero Harju, Lecture Notes on Combinatorial Structures in Graph Theory, Theorem 5.1 and Section 5.2 (standard reference, not scraped)