LemmaStatement: AI-adaptedProof: 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.

Every nonroot vertex has a unique parent, and adjacent vertices have depths differing by one

Statement

In a rooted tree $(T, r)$ , every vertex other than $r$ has exactly one parent. If $u v \in E (T)$ , then the depths of $u$ and $v$ differ by exactly one.

Facts & Assumptions

Given: A rooted tree $(T, r)$ .

[L1]

There is a unique path from $r$ to each vertex (Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity).

[F1]

Depth is distance from $r$ , and parent means the preceding vertex on the root path (Rooted trees, ancestors, descendants, depth, height, parents and children, Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention).

Proof

technique · direct

1.1

For $v \neq r$ , its unique root path has positive length and therefore has one vertex immediately before $v$ . This vertex is the unique parent of $v$ .

L1F1

1.2

Let $u v$ be an edge. The root paths of $u$ and $v$ cannot diverge before their endpoints, since the two divergent tails together with $u v$ would form a cycle. Hence one root path is obtained from the other by appending $u v$ .

2.1

Their lengths, and therefore their depths, differ by exactly one.

step 1.2F1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 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)