# 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`

.