TreesTheoremsRooted trees-ary treesCounting verticesTheoremsSpanning trees of undirected graphsTheoremsPrim's algorithm

A **tree** is a connected simple undirected graph with no simple
circuits.

A **forest** is a (not necessarily connected) simple undirected
graph with no simple circuits.

A graph is a **tree** iff there is a **unique** simple path between any two vertices of .

Every tree, with , has at least two vertices that have degree 1.

Every tree with vertices has exactly edges.

A **rooted tree** is a pair where is a tree, and is a chosen **root** vertex of the tree. Often, the edges of a rooted tree are viewed as being directed:

For each node the **parent** is the unique vertex such that . is then called a **child** of . Two vertices with the same parent are called **siblings**.

A **leaf** is a vertex with no children. Non-leaves are called **internal vertices**. In the example above, are leaves.

The **height** of a rooted tree is the length of the longest directed path from the root to any leaf. In the example above, the height of the graph is .

The **ancestors** of a vertex are all vertices such that there is a directed path from to . In the example above, the ancestors of are and .

The **descendants** of a vertex are all vertices such that there is a directed path from to . In the example above, the descendants of are every other vertex in the graph.

The **subtree** rooted at , is the subgraph containing and all its descendants, and all directed edges between them.

For , a rooted tree is called a **-ary tree** if every internal node has at most children.

It is called a **full -ary tree** if every internal node has exactly children.

An -ary tree with is called a **binary tree**.

are **full** binary, 3-ary and 5-ary trees (respectively). is a **non-full** 3-ary tree, as not every internal node has exactly 3 children.

**Note that the root node is considered an internal node**.

, every full -ary tree with internal vertices has exactly vertices.

Proof:Every vertex other than the root is a child of an internal vertex. There are thus such children, plus root.

a full -ary tree with:

- vertices has internal vertices and leaves.
- internal vertices has vertices and leaves.
- If , then if the -ary tree has leaves then it has vertices and internal vertices.

Proof:All of these can be derived from and .

There are at most leaves in an -ary tree of height .

Proof:By induction on .

If an -ary tree has leaves, and is its height, then .

Proof:Since , we have . But , so .

For a simple undirected graph , a **spanning tree** of is a subgraph of such that is a tree and contains every vertex of .

The blue heavy edges in this grid graph represent a spanning tree.

Every connected graph has a spanning tree.

Proof:While there is a circuit in , remove one edge of the circuit. Repeat until there are no more circuits. Removing one edge of the circuit does not change connoectivity, and eventually no circuits can remain (because there are finitely many edges to be removed). So the end result is a tree which is a subtree of .

Prim's algorithm finds a minimum spanning tree for a weighted undirected graph. This means it find a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.