How to contact me.
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
If T is a tree, then
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
polynomial or computed efficiently
Last modified January 18, 1996, by S.C. Locke.