Some basic Theorems about Graphs in Exercises: Part 13.
--
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 andT
be a spanning tree. Show that the complement ofT
contains at least one edge ofG
.