= Rooted tree leaf
{title2=$\operatorname{outdeg}(v)=0$}
= Leaf of a rooted tree
{synonym}
= Leaves of a rooted tree
{synonym}
A node with no <children in a rooted tree>. This depends on the chosen root: the root of a nontrivial <tree> can have undirected <vertex degree> one while still having a child and therefore not being a leaf in the rooted sense. In a single-node <rooted tree>, the root is a leaf. The distinction matters when counting the complement of the <internal vertices of a rooted tree>.
With every edge directed away from the <root of a tree>, a <rooted tree leaf> has <outdegree> zero.<Graph Theory by Reinhard Diestel>[Third edition2005, section1.5, p.15: rooted tree-order and its maximal elements]{ref}
For an original example, take $E=\{ra,ab,ac\}$ and choose root$r$. The children of$r$ consist of$a$, and the children of$a$ are$b,c$. Thus$b,c$ are the rooted leaves. Vertex$r$ has undirected degree one but has a child, so it is not a rooted leaf in this rooting.
For a nonroot vertex$v$, one incident edge goes to its <parent in a rooted tree>, and all remaining incident edges go to children. Therefore
$$
\operatorname{outdeg}(v)=\deg(v)-1\qquad(v\ne r).
$$
The root instead satisfies $\operatorname{outdeg}(r)=\deg(r)$. A nonroot vertex is consequently a rooted leaf exactly when its undirected degree is one. The root is a rooted leaf exactly when the entire connected tree has one vertex.
Changing the root can change leaf membership without changing any edge. On the three-vertex path$a,b,c$, rooting at$a$ gives one rooted leaf$c$, while rooting at$b$ gives two, $a,c$.
A finite rooted tree always has a leaf: take a vertex maximizing its <graph distance> from the root. Any child would lie one edge farther away, contradicting maximality. An infinite ray rooted at its endpoint has a child at every vertex and supplies the corresponding counterexample to an unrestricted infinite-tree claim. Rooted terminal points and endpoints of an unrooted graph therefore need their conventions stated explicitly.
Back to article page
