= Tree
{disambiguate=graph theory}
{wiki}
= Tree
{synonym}
A <tree> is a nonempty <connected graph> containing no <graph cycle>. Think of seven locations joined so that everyone can reach everyone else, but no connection supplies an alternative route. For a finite <simple graph> with $n\geq1$ <vertices>, three descriptions are equivalent: being a <tree>; having exactly one simple <graph path> between every pair of distinct <vertices>; and being a <connected graph> with exactly $n-1$ <edges>. Here a simple <graph path> repeats no <vertex>. Connectedness in the last description is essential. https://www.maths.tcd.ie/~dwilkins/Courses/MA2C03/MA2C03Courseware_2014to15/MA2C03_S4_Yr1415.pdf[Trinity College Dublin, graph theory notes, Theorems 4.24–4.26 and Corollary 4.27]{ref}
For a concrete <tree>, label the <vertices> $1,\ldots,7$ and take the <edges>
$$
E=\{12,13,24,25,36,67\},
$$
where $ij$ abbreviates the unordered pair $\{i,j\}$. There are seven <vertices> and six <edges>. The unique <graph path> from $4$ to $7$ is $4,2,1,3,6,7$, using five <edges>. The <degree sequence> in label order is $(2,3,2,1,1,2,1)$: its sum is $12=2\cdot6$, as the <degree-sum formula> predicts. Each of $4,5,7$ is a <leaf of a graph>, having <vertex degree> one.
\Image[/tree-unique-paths.png]
{title=A seven-<vertex> <tree>: one <graph path>, two <connected components of a graph> after deletion, and one <graph cycle> after insertion}
Deleting <edge> $13$ leaves precisely two <connected components of a graph>, on $\{1,2,4,5\}$ and $\{3,6,7\}$. Every <edge> of a <tree> is a <bridge in a graph>. Instead add <edge> $57$ to the original <tree>: it closes the unique existing <graph path> $5,2,1,3,6,7$ into exactly one <graph cycle>. Thus a <tree> provides economical connections with no redundancy: a single failed link separates locations. Every finite <tree> with at least two <vertices> has at least two instances of a <leaf of a graph>; the endpoints of a longest <graph path> supply them. https://www.mathstat.dal.ca/~janssen/2113/notes/class14/[Dalhousie University, Trees: leaves and indispensable edges]{ref}
The number $n-1$ alone proves nothing about connectedness: a <cycle graph> on $1,\ldots,6$ together with an isolated <vertex> $7$ has seven <vertices> and six <edges>, yet is disconnected. Briefly, two different simple <graph paths> between the same <vertices> would contain a <graph cycle>. Repeatedly removing a <leaf of a graph> and its incident <edge> proves the <tree> count $n-1$ by <mathematical induction>, starting with one <vertex> and no <edges>.
Back to article page
