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.

✓ 12 results · all verified · 0 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 12 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Induced Subgraphs and Hereditary Graph Classes — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-01Open item page →

$K_{3}$ contains $P_{3}$ as a subgraph but not as an induced subgraph

Statement refuted

Every ordinary subgraph copy of $H$ in $G$ is an induced copy.

Facts & Assumptions

Given: The graphs $P_{3}$ and $K_{3}$ .

[F1]

Deleting one edge from $K_{3}$ leaves a spanning subgraph isomorphic to $P_{3}$ (Subgraphs, induced subgraphs and spanning subgraphs, Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

An induced embedding must preserve both adjacency and nonadjacency (Induced embeddings and induced copies of a graph).

Counterexample

technique · direct

1.1

By deleting one triangle edge, $K_{3}$ contains an ordinary subgraph copy of $P_{3}$ .

1.2

Any injection from the three vertices of $P_{3}$ to the three vertices of $K_{3}$ is bijective, but the two endpoints of $P_{3}$ are nonadjacent while their images in $K_{3}$ are adjacent.

2.1

Thus $K_{3}$ contains no induced $P_{3}$ , despite containing an ordinary subgraph copy.

step 1.1step 1.2∎

Remarks


\draw[->,line width=.9pt] (2.9,.68)--node[above,font=\scriptsize] {delete $02$} (4.25,.68);

\node[vertex] (p0) at (4.75,0) {$0$}; \node[vertex] (p1) at (5.95,1.35) {$1$}; \node[vertex] (p2) at (7.15,0) {$2$}; \draw[edge] (p0)--(p1)--(p2); \draw[gray!65,dashed,line width=.8pt] (p0)--node[below,font=\scriptsize] {deleted} (p2); \node[caption] at (5.95,-.65) {an ordinary $P_3$ subgraph\\not induced}; \end{tikzpicture} ```

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

${ind}_{K_{2}} (G) = 2 ∣ E (G) ∣$ under the induced-embedding convention

Statement

For every finite simple graph $G$ ,

${ind}_{K_{2}} (G) = 2 ∣ E (G) ∣ .$

Facts & Assumptions

Given: A finite simple graph $G$ .

[F1]

${ind}_{K_{2}} (G)$ counts induced embeddings of the two labelled vertices of $K_{2}$ into $G$ (The induced-embedding count ${ind}_{H} (G)$ , Induced embeddings and induced copies of a graph).

[L1]

The sum of vertex degrees is $2 ∣ E (G) ∣$ (Handshake lemma: the sum of the vertex degrees is twice the number of edges).

Verification

technique · direct

1.1

An induced embedding of $K_{2}$ is exactly an ordered adjacent pair $(u, v)$ of vertices of $G$ .

2.1

Counting ordered adjacent pairs by their first vertex gives $\sum_{u \in V (G)} \deg (u)$ .

step 1.1

3.1

By the handshake lemma this is $2 ∣ E (G) ∣$ , proving the formula.

step 2.1L1∎

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

Complete graphs form the hereditary class with forbidden basis ${{\overline{K}}_{2}}$

Statement

The class of finite complete graphs is hereditary, and its minimal forbidden induced-subgraph basis is ${{\overline{K}}_{2}}$ .

Facts & Assumptions

Given: The class $K$ of finite complete graphs.

[F1]

Every induced subgraph of a complete graph is complete (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

A graph is not complete exactly when it has two nonadjacent vertices.

[F3]

A minimal forbidden graph is outside the class while all proper induced subgraphs are inside (Minimal forbidden induced subgraphs and forbidden bases).

[L1]

A hereditary class is determined by its unique minimal forbidden basis (Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs).

[F4]

Heredity means closure under isomorphism and induced subgraphs (Hereditary graph classes).

Verification

technique · direct

1.1

The class $K$ is isomorphism-closed and closed under induced subgraphs, so it is hereditary.

F1F4

1.2

The graph ${\overline{K}}_{2}$ is not complete, while each of its proper induced subgraphs is $K_{0}$ or $K_{1}$ and is complete. Thus it is minimally forbidden.

1.3

Every noncomplete graph has two nonadjacent vertices, and they induce ${\overline{K}}_{2}$ . Hence avoiding ${\overline{K}}_{2}$ is equivalent to being complete.

2.1

Therefore ${{\overline{K}}_{2}}$ is the unique minimal forbidden basis of $K$ .

step 1.1step 1.2step 1.3L1∎

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

Edgeless graphs form the hereditary class with forbidden basis ${K_{2}}$

Statement

The class of finite edgeless graphs is hereditary, and its minimal forbidden induced-subgraph basis is ${K_{2}}$ .

Facts & Assumptions

Given: The class $E$ of finite edgeless graphs.

[L1]

Complete graphs have minimal forbidden basis ${{\overline{K}}_{2}}$ (Complete graphs form the hereditary class with forbidden basis ${{\overline{K}}_{2}}$ ).

[L2]

Complementation preserves hereditary classes and complements their minimal forbidden bases (Complementation preserves hereditary classes and complements their minimal forbidden bases).

[F1]

Complements of complete graphs are edgeless, and $\overline{{\overline{K}}_{2}} = K_{2}$ (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct

1.1

The class $E$ is the complement class of the complete graphs.

2.1

Therefore it is hereditary and its basis is obtained by complementing ${\overline{K}}_{2}$ .

step 1.1L1L2

3.1

That complement is $K_{2}$ , so the basis is ${K_{2}}$ .

step 2.1F1∎

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

A graph is $P_{3}$ -free if and only if every connected component is complete

Statement

A finite graph is $P_{3}$ -free if and only if each of its connected components is complete. Such graphs are called cluster graphs.

Facts & Assumptions

Given: A finite graph $G$ .

[F1]

$P_{3}$ -free means having no induced copy of the three-vertex path ( $H$ -free and $F$ -free graphs under the induced-subgraph convention, Induced embeddings and induced copies of a graph).

[L1]

Connected components partition the vertices and contain every path between their vertices (The connected components of a graph partition its vertex set and are its maximal connected subgraphs).

[F2]

$P_{3}$ has two consecutive edges and no edge between its endpoints (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct

1.1

If every component is complete, three vertices in one component induce all three edges, while vertices meeting more than one component induce edges only within their component parts and therefore at most one edge. Neither pattern is $P_{3}$ , so $G$ is $P_{3}$ -free.

L1F1F2

1.2

Conversely, suppose a component contains nonadjacent vertices $x, y$ . Choose a shortest $x$ - $y$ path $x = v_{0}, v_{1}, \dots, v_{k} = y$ , where $k \geq 2$ .

chooseL1

2.1

Minimality of the path gives $v_{0} v_{2} \notin E (G)$ , so $G [{v_{0}, v_{1}, v_{2}}] ≅ P_{3}$ .

step 1.2F2

3.1

Therefore a $P_{3}$ -free graph cannot have a noncomplete component. Combining both directions proves the equivalence.

step 1.1step 2.1F1∎

Remarks


\node[vertex] (d) at (4.1,.65) {}; \node[vertex] (e) at (5.55,.65) {}; \draw[edge] (d)--(e); \node[caption] at (4.825,-.65) {complete component $K_2$};

\node[caption] at (2.85,-1.25) {$K_3\mathbin{\dot\cup}K_2$ is a cluster graph and is $P_3$-free}; \end{tikzpicture} ```

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-01Open item page →

The class of connected graphs is not hereditary

Statement refuted

The class of connected finite graphs is hereditary.

Facts & Assumptions

Given: The path $P_{3} = v_{0} v_{1} v_{2}$ .

[F1]

$P_{3}$ is connected (Connected graphs and connected components defined by the existence of vertex paths, Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

The induced subgraph on ${v_{0}, v_{2}}$ has no edge (Subgraphs, induced subgraphs and spanning subgraphs).

[F3]

A hereditary class must contain every induced subgraph of each member (Hereditary graph classes).

Counterexample

technique · direct

1.1

The graph $P_{3}$ belongs to the class of connected graphs.

1.2

Its induced subgraph on the endpoints is ${\overline{K}}_{2}$ , which is disconnected.

2.1

Hence this class is not closed under induced subgraphs and is not hereditary.

step 1.1step 1.2F3∎

Remarks


\draw[->,line width=.9pt] (3.55,0)--node[above,font=\scriptsize] {induce on $\{v_0,v_2\}$} (5.25,0);

\node[vertex] (w0) at (5.8,0) {$v_0$}; \node[vertex] (w2) at (7.3,0) {$v_2$}; \node[caption] at (6.55,-.75) {$\overline K_2$ is disconnected}; \end{tikzpicture} ```

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-01Open item page →

The class of regular graphs is not hereditary

Statement refuted

The class of finite regular graphs is hereditary.

Facts & Assumptions

Given: The cycle $C_{4} = v_{0} v_{1} v_{2} v_{3} v_{0}$ .

[F1]

Every vertex of $C_{4}$ has degree two, so $C_{4}$ is regular (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree, Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

The induced subgraph on ${v_{0}, v_{1}, v_{2}}$ is $P_{3}$ (Subgraphs, induced subgraphs and spanning subgraphs).

[F3]

A hereditary class is closed under induced subgraphs (Hereditary graph classes).

Counterexample

technique · direct

1.1

The graph $C_{4}$ is regular.

1.2

Its displayed induced $P_{3}$ has degrees $1, 2, 1$ , so it is not regular.

2.1

Thus regular graphs are not closed under induced subgraphs and do not form a hereditary class.

step 1.1step 1.2F3∎

Remarks


\draw[->,line width=.9pt] (2.1,.75)--node[above,font=\scriptsize] {$G[\{v_0,v_1,v_2\}]$} (4.05,.75);

\node[chosen] (w0) at (4.55,0) {$v_0$}; \node[chosen] (w1) at (5.75,1.5) {$v_1$}; \node[chosen] (w2) at (6.95,0) {$v_2$}; \draw[edge] (w0)--(w1)--(w2); \node[caption] at (5.75,-.65) {$P_3$: degrees $1,2,1$}; \end{tikzpicture} ```

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

$P_{4}$ is both connected and anticonnected

Statement

The path $P_{4}$ is connected and anticonnected. Indeed, $\overline{P_{4}} ≅ P_{4}$ .

Facts & Assumptions

Given: $P_{4}$ with vertices $1, 2, 3, 4$ and edges $12, 23, 34$ .

[F1]

A path is connected (Connected graphs and connected components defined by the existence of vertex paths, Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

A graph is anticonnected when its complement is connected (Anticonnected graphs and anticonnected components).

[F3]

Complement edges are precisely the nonedges between distinct vertices (Graph isomorphisms, automorphisms and graph complements).

Verification

technique · direct

1.1

The graph $P_{4}$ is connected.

1.2

Its complement has edges $13, 14, 24$ , which form the path $3, 1, 4, 2$ . Thus $\overline{P_{4}} ≅ P_{4}$ and is connected.

2.1

Therefore $P_{4}$ is anticonnected as well as connected.

step 1.1step 1.2F2∎

Remarks


\draw[<->,line width=.9pt] (4.2,0)--node[above,font=\scriptsize] {complement} (5.7,0);

\node[vertex] (b3) at (6.15,0) {$3$}; \node[vertex] (b1) at (7.4,0) {$1$}; \node[vertex] (b4) at (8.65,0) {$4$}; \node[vertex] (b2) at (9.9,0) {$2$}; \draw[edge] (b3)--(b1)--(b4)--(b2); \node[caption] at (8.025,-.7) {$\overline{P_4}$: edges $13,14,24$}; \end{tikzpicture} ```

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

Complete, anticomplete and mixed vertex-set pairs in $P_{4}$

Statement

In the path $P_{4} = 1, 2, 3, 4$ :

$({2}, {1, 3})$ is complete;
$({1}, {3, 4})$ is anticomplete; and
$({2}, {3, 4})$ is mixed.

Facts & Assumptions

Given: $P_{4}$ with edge set ${12, 23, 34}$ .

[F1]

Complete means all cross pairs are edges, anticomplete means none are edges, and mixed means some but not all are edges (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

[F2]

The only edges of the path are consecutive pairs (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct

1.1

Both $21$ and $23$ are edges, so $({2}, {1, 3})$ is complete.

F1F2

1.2

Neither $13$ nor $14$ is an edge, so $({1}, {3, 4})$ is anticomplete.

F1F2

1.3

The pair $23$ is an edge but $24$ is not, so $({2}, {3, 4})$ is mixed.

F1F2

2.1

These verify the three claimed pair types.

step 1.1step 1.2step 1.3∎

Remarks


% Anticomplete pair. \node[aset] (a1) at (4.25,0) {$1$}; \node[vertex] (a2) at (5.25,0) {$2$}; \node[bset] (a3) at (6.25,0) {$3$}; \node[bset] (a4) at (7.25,0) {$4$}; \draw[edge] (a1)--(a2)--(a3)--(a4); \node[caption] at (5.75,-.65) {$A=\{1\}$, $B=\{3,4\}$\\anticomplete};

% Mixed pair. \node[vertex] (m1) at (8.5,0) {$1$}; \node[aset] (m2) at (9.5,0) {$2$}; \node[bset] (m3) at (10.5,0) {$3$}; \node[bset] (m4) at (11.5,0) {$4$}; \draw[edge] (m1)--(m2)--(m3)--(m4); \node[caption] at (10,-.65) {$A=\{2\}$, $B=\{3,4\}$\\mixed};

\node[font=\scriptsize,blue!70!black] at (4.55,1.0) {blue: $A$}; \node[font=\scriptsize,orange!80!black] at (6.95,1.0) {orange: $B$}; \end{tikzpicture} ```

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-01Open item page →

Every hereditary graph class has a finite forbidden induced-subgraph basis

False Statement

Every hereditary graph class has a finite minimal forbidden induced-subgraph basis.

Facts & Assumptions

Given: The hereditary class $B$ of finite bipartite graphs.

[L1]

A graph is bipartite if and only if it contains no odd cycle (A bipartite graph and a proper two-colouring of its vertices, A finite graph is bipartite if and only if it has no odd cycle).

[F1]

For every $k \geq 1$ , $C_{2 k + 1}$ is an odd cycle, and distinct lengths give nonisomorphic graphs (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F2]

A minimal forbidden induced subgraph is outside the class while all proper induced subgraphs are inside (Minimal forbidden induced subgraphs and forbidden bases).

[L2]

The family of all such minimal graphs is the unique minimal basis (Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs).

Refutation

technique · contradiction

1.1

Suppose the minimal forbidden basis of $B$ is finite.

assume-contra

1.2

For every $k \geq 1$ , the graph $C_{2 k + 1}$ is not bipartite. Every proper induced subgraph of this chordless cycle is a disjoint union of paths, hence is bipartite. Thus $C_{2 k + 1}$ is minimally forbidden.

L1F1F2

2.1

The minimal basis therefore contains the pairwise nonisomorphic graphs $C_{3}, C_{5}, C_{7}, \dots$ .

step 1.2L2

3.1

This is an infinite family, contradicting step 1.1. Hence a hereditary class need not have a finite minimal forbidden basis.

step 1.1step 2.1discharge-contradiction∎

Remarks


% C_5. \node[vertex] (b1) at (3.2,1.3) {}; \node[vertex] (b2) at (4.35,.35) {}; \node[vertex] (b3) at (3.9,-1.0) {}; \node[vertex] (b4) at (2.5,-1.0) {}; \node[vertex] (b5) at (2.05,.35) {}; \draw[edge] (b1)--(b2)--(b3)--(b4)--(b5)--cycle; \node[caption] at (3.2,-1.55) {$C_5$};

% C_7. \node[vertex] (c1) at (6.7,1.35) {}; \node[vertex] (c2) at (7.8,.85) {}; \node[vertex] (c3) at (8.05,-.35) {}; \node[vertex] (c4) at (7.3,-1.3) {}; \node[vertex] (c5) at (6.1,-1.3) {}; \node[vertex] (c6) at (5.35,-.35) {}; \node[vertex] (c7) at (5.6,.85) {}; \draw[edge] (c1)--(c2)--(c3)--(c4)--(c5)--(c6)--(c7)--cycle; \node[caption] at (6.7,-1.85) {$C_7$};

\node[font=\Large] at (9.2,0) {$\cdots$}; \node[caption] at (4.6,-2.45) {$C_3,C_5,C_7,\ldots$ are the pairwise nonisomorphic minimal forbidden graphs}; \end{tikzpicture} ```

False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-01Open item page →

Every hereditary graph class is closed under taking arbitrary subgraphs

False Statement

Every hereditary graph class is closed under taking arbitrary, not necessarily induced, subgraphs.

Facts & Assumptions

Given: The hereditary class $K$ of complete graphs.

[L1]

Complete graphs form a hereditary class (Complete graphs form the hereditary class with forbidden basis ${{\overline{K}}_{2}}$ ).

[L2]

$K_{3}$ contains $P_{3}$ as an ordinary subgraph but not as an induced subgraph ( $K_{3}$ contains $P_{3}$ as a subgraph but not as an induced subgraph).

[F1]

Heredity requires closure under induced subgraphs, not arbitrary edge-deleted subgraphs (Hereditary graph classes).

Refutation

technique · direct

1.1

The graph $K_{3}$ belongs to $K$ .

1.2

Deleting one edge gives an ordinary subgraph $P_{3}$ , which is not complete and hence does not belong to $K$ .

2.1

Therefore the hereditary class $K$ is not closed under arbitrary subgraphs.

step 1.1step 1.2F1∎

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

Complementary hereditary classes have complementary forbidden bases

Statement

The class of edgeless graphs is complementary to the class of complete graphs, and their minimal forbidden bases ${K_{2}}$ and ${{\overline{K}}_{2}}$ are complementary.

Facts & Assumptions

Given: The classes $K$ of complete graphs and $E$ of edgeless graphs.

[L1]

$B (K) = {{\overline{K}}_{2}}$ (Complete graphs form the hereditary class with forbidden basis ${{\overline{K}}_{2}}$ ).

[L2]

$B (E) = {K_{2}}$ (Edgeless graphs form the hereditary class with forbidden basis ${K_{2}}$ ).

[L3]

Complementation complements the minimal basis of a hereditary class (Complementation preserves hereditary classes and complements their minimal forbidden bases).

[F1]

A graph belongs to the complement class of $K$ exactly when its complement belongs to $K$ .

Verification

technique · direct

1.1

Complementing a complete graph gives an edgeless graph and vice versa, so $E = \overline{K}$ .

1.2

The two basis graphs satisfy $\overline{{\overline{K}}_{2}} = K_{2}$ .

L1L2

2.1

Thus the displayed bases are complementary, exactly as the general theorem predicts.

step 1.1step 1.2L3∎

Remarks


\draw[<->,line width=.9pt] (2.05,0)--node[above,font=\scriptsize] {complement} (3.55,0);

\node[vertex] (b1) at (4.1,0) {}; \node[vertex] (b2) at (5.6,0) {}; \draw[edge] (b1)--(b2); \node[caption] at (4.85,-.7) {$K_2\in\mathcal B(\mathcal E)$}; \end{tikzpicture} ```

Induced Subgraphs and Hereditary Graph Classes — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

K3K3​ contains P3P3​ as a subgraph but not as an induced subgraph

Statement refuted

Facts & Assumptions

Counterexample

Remarks

ind⁡K2(G)=2∣E(G)∣indK2​​(G)=2∣E(G)∣ under the induced-embedding convention

Statement

Facts & Assumptions

Verification

Complete graphs form the hereditary class with forbidden basis {K‾2}{K2​}

Statement

Facts & Assumptions

Verification

Edgeless graphs form the hereditary class with forbidden basis {K2}{K2​}

Statement

Facts & Assumptions

Verification

A graph is P3P3​-free if and only if every connected component is complete

Statement

Facts & Assumptions

Verification

Remarks

The class of connected graphs is not hereditary

Statement refuted

Facts & Assumptions

Counterexample

Remarks

The class of regular graphs is not hereditary

Statement refuted

Facts & Assumptions

Counterexample

Remarks

P4P4​ is both connected and anticonnected

Statement

Facts & Assumptions

Verification

Remarks

Complete, anticomplete and mixed vertex-set pairs in P4P4​

Statement

Facts & Assumptions

Verification

Remarks

Every hereditary graph class has a finite forbidden induced-subgraph basis

False Statement

Facts & Assumptions

Refutation

Remarks

Every hereditary graph class is closed under taking arbitrary subgraphs

False Statement

Facts & Assumptions

Refutation

Complementary hereditary classes have complementary forbidden bases

Statement

Facts & Assumptions

Verification

Remarks

Sources

$K_{3}$ contains $P_{3}$ as a subgraph but not as an induced subgraph

${ind}_{K_{2}} (G) = 2 ∣ E (G) ∣$ under the induced-embedding convention

Complete graphs form the hereditary class with forbidden basis ${{\overline{K}}_{2}}$

Edgeless graphs form the hereditary class with forbidden basis ${K_{2}}$

A graph is $P_{3}$ -free if and only if every connected component is complete

$P_{4}$ is both connected and anticonnected

Complete, anticomplete and mixed vertex-set pairs in $P_{4}$