Construct a proof that a connected simple graph has a spanning tree by putting these steps in order, top to bottom.

Initially, suppose that G is a connected simple graph. If G is not a tree, it must contain at least one simple circuit. This subgraph is connected because any two vertices connected by a path containing the removed edge are connected by a path not containing this edge. A tree is produced because the graph stays connected as edges are removed. This tree is a spanning tree because it contains every vertex of G. lf this subgraph is not a tree, it has another simple circuit. Repeat the process of removing edges until no simple circuits remain. Remove an edge from one of these simple circuits, which creates a subgraph that has one less edge than G but still contains all the vertices of G