1
$\begingroup$

When proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle, is it sufficient to just remove that edge that created a cycle, then it since that results in a graph with no cycles, therefore it must be a tree graph by definition?

Original statement to prove: Prove a simple connected graph T is a tree if and only if adding an edge between two existing vertices of T creates exactly one cycle.

|cite|improve this question
$\endgroup$
  • $\begingroup$ If only you want to prove the implication, not the equivalence. $\endgroup$ – gukoff Mar 9 '13 at 6:22
  • $\begingroup$ How do you deal with the complete graph? $\endgroup$ – Michael Biro Mar 9 '13 at 7:28
2
$\begingroup$

The proof is not valid because it fails to prove that the graph is acyclic. The non sequitur is in the following:

$\dots$just remove that edge that created a cycle, then it since that results in a graph with no cycles

Notice that the statement doesn't follow. Also, notice that adding an edge to any connected graph will create a cycle. You must use the fact that exactly $1$ cycle is generated as a result.

Hint: Argue by contradiction. Assume the graph has a cycle. When you connect two vertices of the cycle, how many cycles are created?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Ok..so can I use what I wrote as a proof or what for the converse $\endgroup$ – DJ_ Mar 9 '13 at 6:00
  • $\begingroup$ Sorry, I had misread the question, and it took me a few minutes to regain my composure. $\endgroup$ – A.S Mar 9 '13 at 6:23
  • 1
    $\begingroup$ For proving if T is a tree then adding an edge between 2 vertices creates exactly one cycle I used the definition that 2 vertices in T have exactly one path and so if I add a new edge it creates exactly one cycle. For the converse I did, since there is only one cycle in graph there is two paths from v to w in T, so if I remove one edge, the number of paths from v to w decreases by 1, so then its a tree. Sooo I can't remove an edge and just say the number of paths from v to w decreased to 1? $\endgroup$ – DJ_ Mar 9 '13 at 6:52
  • $\begingroup$ The problem is that the hypothesis does not tell you that there is one cycle in the entire graph. It only tells you that adding an edge adds exactly $1$ cycle to the graph. $\endgroup$ – A.S Mar 9 '13 at 6:53
  • $\begingroup$ well its an if and only if statement, don't I have to prove if adding an edge between two existing vertices of T creates exactly one cycle $\endgroup$ – DJ_ Mar 9 '13 at 6:56
1
$\begingroup$

Hint:

  • Prove that if connected graph $G = (V,E)$ contains a cycle and it is not a clique, then you can always add an edge that will create at least two cycles.
  • Let $C \subset E$ be some cycle and $u \notin C$ be a vertex such that there exists two vertices $v_1, v_2 \in C$ with $uv_i \notin E$. Then one of $uv_i$ would create at least two cycles.
  • If the previous step is not possible, then the graph is a clique or a clique without a single edge (and adding this missing edge surely would create at least two cycles).

Good luck!

|cite|improve this answer
$\endgroup$

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.