ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-01

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.

The isomorphism types of trees on at most five vertices

Statement

Up to isomorphism, the numbers of trees on $1, 2, 3, 4, 5$ vertices are respectively $1, 1, 1, 2, 3$ . Representatives are

$K_{1}; K_{2}; P_{3}; P_{4}, K_{1, 3}; P_{5}, K_{1, 4}, and the tree with degree sequence (3, 2, 1, 1, 1) .$

Facts & Assumptions

Given: A tree $T$ on at most five vertices.

[L1]

A tree on $n$ vertices has $n - 1$ edges and, for $n \geq 2$ , at least two leaves (A tree on $n \geq 1$ vertices has $n - 1$ edges, Every tree with at least two vertices has at least two leaves).

[L2]

The sum of degrees is twice the number of edges (Handshake lemma: the sum of the vertex degrees is twice the number of edges).

[F1]

Isomorphisms preserve degrees (Graph isomorphisms, automorphisms and graph complements).

[F2]

$K_{n}$ , $K_{1, n}$ and $P_{n}$ have their standard edge sets (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · cases by $n$ and maximum degree

1.1

In the case $n \leq 3$ , connectedness and the edge count force $K_{1}, K_{2}, P_{3}$ , respectively.

assume-case smallL1F2

1.2

In the case $n = 4$ , maximum degree two forces the connected acyclic graph $P_{4}$ , while maximum degree three forces $K_{1, 3}$ . These degree sequences differ, so the two are nonisomorphic.

assume-case fourL1L2F1

1.3

In the case $n = 5$ , maximum degree two gives $P_{5}$ , maximum degree four gives $K_{1, 4}$ , and maximum degree three forces degree sequence $(3, 2, 1, 1, 1)$ by the degree sum $8$ .

assume-case fiveL1L2

2.1

Each displayed degree sequence determines the indicated tree: attach all remaining vertices to the unique high-degree vertex, with the degree-two vertex extending one arm in the third case.

step 1.3L1

3.1

The representatives in each row have different degree sequences, so they are pairwise nonisomorphic and the list is complete.

step 1.1step 1.2step 1.3step 2.1F1cases-exhaustive∎

Depends on

Used by

Cayley's formula counts unlabelled trees False statement

Dependency tree · two levels

20 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

Reinhard Diestel, Graph Theory, Preview Chapter 1 (standard reference, not scraped)