proof by induction that if G is a connected graph then G con

proof by induction that if G is a connected graph, then G contains a spanning tree.

Solution

Proof:

Case I: Assuming G is a graph that contains a spanning tree.

Let G be a graph that contains a spanning tree, T. Let u and v be vertices in G.

Since T is a spanning tree of G, u and v are also vertices in T. Now, T is a tree, so it is connected.

Thus there is a path from u to v in T. T is, by definition of a spanning tree, a subgraph of G, so the path in T

from u to v is also a path in G. Since u and v were arbitrary vertices in G we see that G is connected.

Case II-   Converse of case I,

Conversely, we assume G is a connected graph.

Here we note that if G is not simple, we may remove all loops and all but one edge between any pair of vertices that has more than one edge between them and the resulting graph will be a simple connected graph.

Thus we may assume without loss of generality that G is simple.

Now we prove by induction.

Let n = |V (G)|. If G has fewer than n 1 edges then it would not be connected, thus |E(G)| n1.

From definition of \"Trees\" we recall that, G is a tree if and only if |E(G)| = n 1, so we assume G has at least n 1 edges, say |E(G)| = (n 1) + k.

We will prove that a connected graph with n vertices and (n1)+k edges contains a spanning tree by induction on k, where k 0.

First Step: If k = 0. Then G is already a tree by our observation above. Induction Step: Assume that every connected graph with n vertices and (n 1) + k edges, k 0, contains a spanning tree.

Suppose G is a connected graph with n vertices and (n 1) + (k + 1) edges. Since |E(G)| > n 1, G is not a tree so there must be a simple circuit in G.

Removing any edge from this circuit will result in a connected subgraph, G1, of G with the same vertex set and n 1 + k edges.

By our induction hypothesis, G1 contains a spanning tree. But since G1 is a subgraph of G containing all of the vertices of G, any spanning tree of G1 is a spanning tree of G.

Thus, G contains a spanning tree. Therefore, by the principle of mathematical induction, every simple connected graph contains a spanning tree.