In this section we consider undirected graphs and their subgraphs. Consider a connected , undirected graph . T is connected.
T is acyclic.
A spanning tree is called a tree because every acyclic undirected graph can be viewed as a general, unordered tree. Because the edges are undirected, any vertex may be chosen to serve as the root of the tree. According to Definition , a spanning tree is connected. Therefore, as long as the tree contains more than one vertex, there can be no vertex with degree zero. Let be a spanning tree of G .