[Math] Adding an edge to a tree creates a cycle – is the proof correct

graph theorytrees

I saw you answered similar questions here, but I wanted to know if
I can prove the theorem (= adding an edge to a tree creates a cycle)
also like this:

It is known that the definition of a tree, is that it's-

1. connected,

2. with no cycles,

3. and with $n$ vertices and $n-1$ edges.

Also, it is known that a cycle has-

* equal number of vertices and edges, suppose-
$n$ edges and $n$ vertices.

Therefore, when we add one edge to a tree, the tree contains now $n$ edges $((n-1)+1),$ and it is exactly the number of its vertices, so it contains a cycle now.

Is this whole proof correct?

Best Answer

A cycle contains the same number of edges as vertices. But not every graph with this property is a cycle, so your final statement is unjustified.

Some six-vertex graphs with six edges you can find on The House of Graphs that aren't cycles are below (there's plenty of other examples if you'd like more).

enter image description here enter image description here enter image description here

You may notice that all of these graphs contain a cycle, and in fact that's generally true, but this is precisely the statement you have to prove.

One approach might be to first find a subgraph which has minimum degree $2$, and then find a cycle inside this subgraph in the usual way.

Also, a final nitpick: usually, only the first two properties you gave (connected and has no cycles) are the definition of being a tree. The third property, of course, is likely to be something you prove about trees fairly early on, starting from that definition.

Related Question