In class we have defined a tree as a connected undirected si

In class, we have defined a tree as a connected undirected simple graph with no cycles, and have shown that a tree with n vertices has n - 1 edges. Show that adding any more edge to a tree will create a cycle.

Solution

Let G be a connected undirected simple graph.

Then G has no cycles and let G have n vertices and n-1 edges,

If n = 1, then no edges and it is a tree.

If n >=2, it has n-1 edges, then the tree has one pendent vertex (vertex of degree 1)

Remove this vertex and the edge then we get another tree with n-1 vertices and n-2 edges.

Thus by induction a tree with n vertices have n-1 edges.

If we add one more edge without increasing the vertices say

then we have n vertices and n edges which means one edge extra connects an existing vertex to another exising vertex.

Already since G was a tree any two vertices would have been connected by a unique path.

Now by adding this new more edge between two vertices we got a cycle which makes G a non tree.

Hence proved.