# Trees

How to contact me.

## Definitions

A graph is *acyclic* if it has no cycles.
An acyclic graph is also called a *forest*.
A *tree* is a connected, acyclic graph.
Thus every connected component of a forest is a tree.
A *spanning tree* of a graph *G* is
a subgraph *T* of *G* which is a tree and
which satisfies
*|V(T)|=V|(G)|*.

## Easy Theorems

If *T* is a tree, then
*|V(T)|=E|(T)|+1*.
Any tree with at least two
vertices must have a vertex of degree one.
Alternately, one could define a tree as a connected graph
*T* satifying *|V(T)|=E|(T)|+1*
or as an acyclic graph
*T* satifying *|V(T)|=E|(T)|+1*.
Every connected graph must have a spanning tree.

The number of spanning trees of a connected graph
can be deduced from the
Tutte
polynomial or computed efficiently
using the
Matrix
Tree Theorem.

Last modified January 18, 1996, by S.C. Locke.