4 Spanning Trees

4.2 ***Spanning Trees and Forests***

Exercise(A) 4.10.

Show that the following are equivalent. Let G be a graph with k components.

  1. 1.

    T⊂G is a spanning forest 22 2 This terminology is a slight abuse of our usual usage of the term ‘spanning’. i.e., a forest such that every component of the forest is a spanning tree of the corresponding compoent.

  2. 2.

    T is a ’minimal’ spanning subgraph with k components. Here minimality of T means that T−e has k+1 components for any e∈T.

  3. 3.

    T is a maximal subgraph without cycles. Here maximality of T means that there is no T′⊋T such that T′ has no cycles.

Exercise 4.11.

Let H⊂G be a subgraph and e∈G∖H. Then exactly one of the following holds : (1) β0⁢(H∪e)=β0⁢(H)−1 or (2) β0⁢(H∪e)=β0⁢(H) and there exists a cycle C⊂H∪e such that e∈C and C∖e is not a cycle in H.

Definition 4.12 (Cut edges and vertices ).

An edge e is a cut-edge in a graph G if β0⁢(G−e)=β0⁢(G)+1. A vertex is a cut-vertex in a graph G if β0⁢(G−v)>β0⁢(G).

Exercise 4.13.

An edge is a cut-edge iff it belongs to no cycle.

Lemma 4.14.

TFAE

  1. 1.

    G is a forest

  2. 2.

    There exists a unique simple path between u to v for all u≠v which are in the same component.

  3. 3.

    Every edge is a cut-edge.

Proof.

Since forest has no cycles, (i) ⇒ (iii) follows from the above exercise. Since every edge is a cut-edge, this implies that there are no cycles and hence G is a forest i.e., (iii) ⇒ (i). If there exists two distinct simple paths from u to v for u≠v in the same component, then the union of the paths contains a cycle (Prove this as an exercise !). This contradicts (i) and (iii). Thus, (i) and (iii) both imply (ii). Assuming (ii), it is easy to see that there is no cycle in G and hence both (i) and (ii) hold. ∎

Lemma 4.15 (Insertion property of Spanning Trees).

Suppose T is a spanning tree of G and there exists e∈G−T. Then ∃e′∈T such that T+e−e′ is also a spanning tree.

eGTT’=T-e’+ee’e’
Figure 4.1: A figure illustrating the insertion property of a spanning tree.
Proof.

For any e′∈T, T+e−e′ has same number of edges as T. Hence it suffices to show that there exists e′ such that T+e−e′ does not have a cycle. This can be seen easily as follows : Since T is a spanning tree, T+e contains a cycle. Now remove any edge e′ in the cycle and we can see that T+e−e′ does not contain a cycle. ∎

Exercise(A) 4.16 (Deletion property of Spanning Trees).

Suppose T,T′ are spanning trees of G and e∈T−T′. Then ∃e′∈T′ such that T−e+e′ is also a spanning tree.