1
$\begingroup$

$G$ is a tree $\iff G$ contains no cycles, but if you add one edge you create exactly one cycle


Could anyone please be so kind to check my proof? That would be very much appreciated. Thank you in advance.

My proof:

'$\rightarrow$' Assume $G$ is a tree. Then by definition it is connected. Furthermore, there is a unique $u, v$-path for every $u,v \text{ in } G$. For arbitrary $u$ and $v$, let this path be $u=u_1\rightarrow u_2\rightarrow \dots \rightarrow u_k=v$. Assume $\nexists$ an edge $e=\{u_i,u_j\}$ for some vertices $u_i, u_j \text{ } (j>i)$ in this path. Now add this edge $e=\{u_i,u_j\}$. Then we can follow the original $u,v$-path until we arrive at $u_j$ and then return to $u_i$ via $e$. Hence this is a cycle.

'$\leftarrow$' Assume $G$ contains no cycles but if you add one edge you create exactly one cycle. To prove that $G$ is a tree we only need to prove connectedness, since it is already given that $G$ contains no cycles. Reason by contradiction. Assume that $G$ is not connected. Then $\exists u \exists v \text{ }(u\neq v)$ in $G$ s.t. $\nexists$ an edge $\{u,v\}$. Add this edge. This will not create a cycle. But this contradicts our original assumption. Hence $G$ must be connected, and thus $G$ is a tree.

$\endgroup$
  • $\begingroup$ One concern that I have is that I have not explicitly incorportated the fact that you create exactly one cycle. I do think it is implicitly there though. Or should that be taken care of in more detail (if so, how?)? $\endgroup$ – dreamer Jun 14 '13 at 20:06
  • $\begingroup$ Looks pretty good, except in the $\leftarrow$ direction you need to choose your $u,v$ more carefully. $\endgroup$ – vadim123 Jun 14 '13 at 20:06
  • $\begingroup$ @vadim123 Thank you. Could you please elaborate on what you mean by 'more carefully'? What should be changed? $\endgroup$ – dreamer Jun 14 '13 at 20:08
  • $\begingroup$ You need $u,v$ to be in different components. You're also right about the "exactly one" in the $\rightarrow$ direction. $\endgroup$ – vadim123 Jun 14 '13 at 20:10
  • $\begingroup$ @vadim123 Thank you for your help. Could you please show me how this should be written down? Also the ''exactly one'' part please, as I could not figure out how I should include that in my proof. $\endgroup$ – dreamer Jun 14 '13 at 20:12
2
$\begingroup$

To prove "exactly one" in the $\rightarrow$ direction, suppose the addition of $(u,v)$ created (at least) two cycles. Both must include $(u,v)$ else they were cycles before. However, we now can go from $u$ to $v$ along two different paths in the tree, a contradiction.

In the $\leftarrow$ direction, if $G$ is not connected, choose $u,v$ from different components. Then adding $(u,v)$ cannot create a cycle.

| 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.