spanning tree

A spanning treeMathworldPlanetmath of a (connected) graph G is a connected, acyclic subgraphMathworldPlanetmath of G that contains all of the vertices of G. Below is an example of a spanning tree T, where the edges in T are drawn as solid lines and the edges in G but not in T are drawn as dotted lines.