A spanning tree of a graph G is a spanning subgraph of G which is a tree (see example in Figure 1.1).

                                                       Figure 1.1. A spanning tree of a graph (in bold)

Proposition 1.1.

 A connected graph G has (at least) one spanning tree.

Proof. Remove from G, if possible, an edge which is not a bridge. On the one hand, the spanning subgraph obtained is always connected since only non-bridge edges were removed from the current graph. On the other hand, this subgraph has no cycle since it no longer has any bridge. Therefore, it is a tree. By construction, it is also a spanning subgraph of G.

Corollary 1.1. If G is connected then m ≥ n − 1,with m = n − 1 if and only if G is a tree.

Proof. Since G is connected, it contains, as a spanning subgraph, a tree T. We have m_G ≥ m_T = n_T − 1= n_G − 1. Since T is a spanning subgraph of G, the equality is possible only if G = T, that is if G is itself a tree.

The two following results will be useful in particular for the application dealt with later on.

Proposition 1.2.

 A spanning subgraph of a connected graph G is a spanning tree of G if and only if it is connected and edge-minimal.

Proof. The necessary condition results from (In a tree, any edge is a bridge.). In order to prove the sufficient condition, let T be a spanning subgraph of G which is connected and minimal. Then for any edge e of T, T − e is no longer connected,that is, e is a bridge of T. Condition (G is connected and every edge is a bridge), applied to T, allows us to conclude.

Proposition 1.3.

A spanning subgraph of a connected graph G is a spanning tree of G if and only if it is acyclic and edge-maximal.

Proof. T is a spanning tree of G. If such anedgeexists, let e be one which does not belong to T. The endvertices of e are linked in T by a path (since T is connected). This path with edge e defines a cycle of T + e. Thus, T is really acyclic and maximal, which proves the necessary condition. Now,  given T a spanning subgraph of G which is acyclic and maximal, to show that T is a spanning tree, and to justify the sufficient condition, we only need to show that T is connected. Let x and y be any two vertices of T and let us show that they are linked by a path of T. Since G is connected, there is a path D of G linking x and y. If this path has all of its edges in T, we are done. If not, let e be an edge of D which is not in T. By hypothesis on T, T + e has a cycle, C. This cycle contains the edge e, and according to lemma (An edge of a graph G is a bridge if and only if it does not belong To a cycle of G.) this edge is not a bridge of T + e, and therefore there is in T a path linking the endvertices u and v of e. By substituting in D edge e by this path, we define a walk linking x and y which has one less edge which is not in T. By repeating this substitution process, as long as there is anedge which is not in T in the walk under consideration linking x and y, we obtain in the end a walk, and so a path (Lemma -In a graph, if two vertices are connected by a walk then they are connected by a path.), of T linking x and y, which ends the proof.

Consider two more useful results (trees have many useful properties!).

Proposition 1.4.

Given a spanning tree T of G and an edge e of G which does not belong to T, the spanning subgraph T + e contains only one cycle.

Proof. First of all, T + e contains a cycle. If the edge e belonged to two distinct cycles, we could deduce in T two distinct paths linking its endvertices x and y, considering these cycles deprived of the edge e. This would contradict proposition (In a tree any two vertices are  connected by a unique path.).

Lemma 1.1 (Exchange lemma).

Given a spanning tree T of G, anedge e of G which does not belong to T and an edge f of the cycle of T + e, then T + e − f is a spanning tree of G.

Proof. In applying condition (2) of theorem 2.1, on the one hand T + e – f is connected because the edge f is not a bridge of T + e since it belongs to a cycle, while on the other hand we have mT+e−f = mT = nT − 1= nT+e−f − 1.

This last result gives an idea of the different spanning trees which exist in a (connected) graph, obtained by exchanging edges (Figure 1.2). It allows the generation of other spanning trees from one of them.

This last result gives an idea of the different spanning trees which exist in a (connected) graph, obtained by exchanging edges (Figure 1.2). It allows the generation of other spanning trees from one of them.

Figure 1.2. Two spanning trees of a graph (in bold); the second one is obtained from the first one by exchanging the two edges e and f The following lemma, which is stronger, will be very helpful later on. The notation T^/ T designates here the set of the edges of T^/ which are notin T. We can likewise define T T^/ .

Lemma 1.2 (Strong exchange lemma).

Given two spanning trees T and T^/of G, andanedge e ∈ T^/ T, there exists an edge f ∈ T T^/such that T + e − f and T^/+ f − e are spanning trees of G.

Proof. By choosing edge f in the cycle of T + e and not belonging to T^/,which is always possible since T^/does not contain any cycles, we will  Have truly that T+e−f is a spanning tree. Nevertheless, this will not necessarily mean that T^/+f −e is also a spanning tree. Edge f must be well  chosen. Graph T^/− e has two connected components, C₁ andC₂. There is necessarily in the cycle of T + e an edge, other than e, whoseendvertices  are one in C₁ and the other in C₂. Let this edge be f.

This edge is thus not in T^/. Edge e is necessarily an edge of the cycle of T^/+ f (because e and f are the only edges of T^/+ f joining C₁ and C₂),and  so T^/+ f − e . Thus wehave found an edge f ∈ T T^/so that T +e−f and T^/ +f −e are spanning trees of G.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(49-52)