# Tree **An undirected [[graph]] in which any two vertices are connected by exactly one [[path]].** ![[TreeGraphTheory.svg|300]] *A tree* > [!Forest] > A *forest* is an undirected graph which contains at most one path between any two vertices. > > Alternatively, a forest is an [[Cycle#^5c9079|acyclic]] undirected graph or also the disjoint union of a set of trees. > [!Tree] > A *tree* is an undirected graph which contains exactly one path between any two vertices. > > Equivalently, a tree is a [[Connected Graph|connected]] acyclic undirected graph. Every tree is a [[Bipartite Graph|bipartite]] and a [[Planar Graph|planar]] graph. An *internal vertex* is a vertex of a tree with a degree of at least 2, whilst a vertex with degree of at least 3 is also a *branch vertex*. An *external vertex*, more commonly known as a *leaf*, has degree of exactly 1. > [!Spanning tree] > A *spanning tree* of a graph $G$ is a subgraph which is a tree and includes all vertices of $G$. Every connected graph contains a spanning tree. > > ![[SpanningTree.svg|300]] > *A spanning tree within the [[complete graph]] $K_{5}$* ### Rooted tree A *rooted tree* is a directed tree with a distinguished vertex known as the *root*. All edges of a rooted tree have some natural orientation relative to the root, either directed towards or away from it. The *parent* of some vertex $v$ is the vertex adjacent to $v$ which is on the path towards the root. A *child* of vertex $v$ is a vertex to which $v$ is a parent. Two vertices with the same parent are known as *siblings*. The root has no parent and the leaves of a rooted tree have no children. The *height* of some vertex is the length of the longest downwards path to a leaf from the vertex. The height of the root is also the height of the tree. The *depth* of some vertex is length of the path from the vertex to the root. A rooted tree in which every vertex contains at most $k$ children is known as a $k$-ary tree. 2-ary and 3-ary trees are commonly known as binary and ternary trees respectively. Rooted trees are the typical form of [[Tree, data structure|tree]] data structures. ![[RootedTree.svg|400]] *A rooted tree of height $4$; the vertex $v$ has a height of $1$ and a depth of $3$*