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…