# 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 and `T` be a spanning tree. Show that the complement of `T` contains at least one edge of `G`.