2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov May 16 '18 at 14:27
  • $\begingroup$ 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 $\endgroup$ – John Quiggin May 16 '18 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.