Some basic Theorems about Graphs in Exercises: Part 13.

Join Medium with my referral link - applied.math.coding

This story belongs to a contiguous series with the aim to list some of the basic theorems of graph theory. It is intentionally written in form of exercises to invite the reader having a ‘learning experience by doing’. In this sense it is not important to have solved any of these exercises but it is important to have tried them for a couple of minutes.

As usually in this series, all graphs are assumed to be simple, undirected and finite, except otherwise mentioned.

Problem 1:

A connected graph G is a tree if and only if it has exactly one spanning tree.

Remember, a tree is a connected graph without cycles. A spanning tree of a graph is a sub-graph that is a tree and contains all the graph’s vertexes.

Solution:

The forth direction is quite easy to see by observing that a spanning tree of a tree must contain all edges of the tree itself since otherwise it would not be connected. On the contrary, if a tree still would be connected after removing an edge, one readily verifies that it would have a cycle.

Let us assume we are given a connected graph G that has only one spanning tree. To the contrary let us assume that G has a cycle. Then there must exist two vertexes u and v and two non-cyclic, disjoint paths P_1, P_2 connecting them. We can easily adjust the construction of a spanning tree given here [problem 3] to start with the vertex u and make it following the path P_1 or P_2 in the first steps. That is, we obtain two spanning trees T_1, T_2 where T_1 contains P_1 and T_2 contains P_2. T_1 cannot contain P_2, otherwise it would contain the cycle P_1 * P_2^-1. Therefore we found two distinct spanning trees, a contradiction!

Problem 2:

Let G be a graph that has at least one cycle and T be a spanning tree. Show that the complement of T contains at least one edge of G.