Definition: Root, Degree of a Tree, Subtree, Height

Let a tree $T$ be given and let $r$ be a designated vertex of that tree called its root. * The subtrees of $T$ (with respect to the root $r$) are the disconnected subgraphs of $T$ when disconnected by removing the root $r.$ * The roots of the subtrees are those uniquely determined vertices, which were adjacent to $r$ before it was removed. * The degree of $T$ (with respect to the root $r$) is the maximum vertex degree of its root and all vertex degrees of roots of its subtrees obtained recursively by removing their roots. * The height of $T$ (with respect to the root $r$) is the maximum length of a path between $r$ and its leaves.


The following figure demonstrates the above concepts and also the fact that they indeed depend on the special choice of the root. You see the same tree drawn in two different ways.


In the left drawing:

In the right drawing:

Definitions: 1
Lemmas: 2
Proofs: 3

Thank you to the contributors under CC BY-SA 4.0!




  1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition