Trees

Definition 3.1

• acyclic: if there are no cycles or circuits in the graph.
• tree: acyclic and connected.
• forest: acyclic graph.
• leaf: vertex with degree 1.

Spanning Trees

Definition 3.2

A spanning tree is a spanning subgraph that is also a tree.

Definition 3.3

• Given a weighted graph $G=(V,E,w)$, $T$ is a minimum spanning tree, or MST, of $G if it is a spanning tree with least total weight.$

Kruskal’s Algorithm

• Just sort all weighted edges and pick the one with least weight until the graph connected and without any cycle.

Prim’s Algorithm

• Randomly pick a root. Add the least weight edge that incident to root. Then find the least weight edge among all edge that incident to the endpoint of $T$ until $T$ cotain all vertex and connected.

Tree Properties

Theorem 3.4

Every tree with at least two vertices has a leaf.

Theorem 3.6

A tree with $n$ vertices has $n-1$ edges $\forall n\ge 1$.

Theorem 3.11

Let $T$ be a graph with $n$ vertices.

$T$ is a tree.
$\iff$ $T$ is acyclic and contain $n-1$ edges.
$\iff$ $T$ is connected and contain $n-1$ edges.
$\iff$ There is a unique path between every pair of distinct vertice in $T$.
$\iff$ $T$ is acyclic and for any edge $e$ from $T$, $T+e$ contains exactly one cycle.

Tree Enumeration

Definition 3.13

Given a tree $T$ on $n \gt 2$ vertices(labeld 1,2,…,n), the Prufer sequence of $T$ is a sequence $(s_{1},s_{2},...,s_{n-2})$ of length $n-2$ defined as follows:

• Let $l_{1}$ be the leaf of $T$ with the smallest label.
• Define $T_{1}$ to be $T-l_{1}$.
• For each $i\ge 1$, define $T_{i+1}=T_{i}-l_{i+1}$, where $l_{i+1}$ is the leaf with the smallest label of $T_{i}$.
• Define $s_{i}$ to be the neighbor of $l_{i}$.