2

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?

Adrian Keister
  • 10,099
  • 13
  • 30
  • 43
Shelly875
  • 25

2 Answers2

3

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.

Misha Lavrov
  • 142,276
2

Informally, you can argue as follows. Any two vertices in a tree are connected by exactly one path. Add an edge e connecting v1 and v2. Then you can reach v1 from itself by following the edge e and the existing path from v2 to v1.

John Quiggin
  • 53
  • Valid, though at the stage where you're proving that adding any edge to a tree creates a cycle, you're likely to want a proof for your first assertion as well. – Misha Lavrov May 16 '18 at 14:27
  • 1
    Yes, Wikipedia uses the path condition as the definition of a tree but if we are starting from the definition in the question, we need to prove equivalence – John Quiggin May 16 '18 at 14:39
  • "Any two vertices in a tree are connected by exactly one path". This can be proved as the following: let arbitrary vertex pair be $(u,v)$ and the path number between them be $p(u,v)$. "connected" implies $p(u,v) \ge 1$. "with no cycles" implies $p(u,v) \le 1$. So we have $p(u,v)=1$. – An5Drama Feb 04 '24 at 10:29
  • BTW, "exactly one path" implies only one cycle is created after adding one edge because 1. trivially this cycle must contain $e$ otherwise the original graph is not one tree. 2. $e$ can be only concatenated with the path $p(v_1,v_2)$ in the original graph to construct one cycle. This is also shown in this QA. – An5Drama Feb 05 '24 at 09:19