DefinitionDefinition: AI-adaptedProof: Not applicableaudited 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.

Rooted trees, ancestors, descendants, depth, height, parents and children

Definition

A rooted tree is a pair $(T, r)$ consisting of a tree $T$ and a distinguished vertex $r$ , the root (Trees, forests, leaves and isolated vertices). The unique $r$ - $v$ path is the root path of $v$ (Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity).

The depth of $v$ is $d_{T} (r, v)$ , and the height of $(T, r)$ is the maximum vertex depth (Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention). A vertex $u$ is an ancestor of $v$ , and $v$ a descendant of $u$ , when $u$ lies on the root path of $v$ . If $v \neq r$ , the neighbour of $v$ immediately preceding it on its root path is its parent; the vertices having parent $v$ are the children of $v$ .

The vertices of depth $k$ form level $k$ . The root has depth zero and is its own ancestor, but it has no parent.

Depends on

Used by

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

Dependency tree · two levels

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