Given a
graph G=(
V,
E), a
spanning tree of
G is a
subset E' of the
edges
E, which
connects all
vertices of
V and is a
tree.
In other words,
- (V,E') is a connected graph.
- (V,E') contains no cycles.
Spanning trees are some kind of "backbone" of a graph.