Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent.

  1. $G$ is a tree.
  2. Any two vertices in $G$ can be connected by a unique simple path.
  3. $G$ is connected, but is not connected if any single edge is removed from $G$.
  4. $G$ has no cycles, and a simple cycle is formed if any edge is added to $G$.

I just would like to know whether my first two steps for my four-part-proof are enough or need improvement to show the implications. If there are any suggestions on what to do better, please let me know. Furthermore I solve this in German, but I would like to improve my English and would be pleased if you could point out some things I could write better.

  • $(1)\implies (2)$: Assume there are two vertices $v,w\in V$ that are not connected by a simple path. Therefore $G$ is not connected which is contrary to the assumption that $G$ is a tree which is connected by definition. (*1)
  • $(2)\implies (4)$: Assume that $G$ does contain a cycle implying that there are at least two vertices $v,w\in V$ such that they are are connected by $j\geq 2$ paths contrary to the assumption that $j\overset{!}{=}1$. (*2)
  • $(4)\implies (3)$: First, we show that $G$ is connected in general, then we will show that there is no way to remove an edge such that $G$ remains connected. Assume that $G$ is not connected and therefore two vertices $v,w\in V$ exist such that they are not connected by a simple path. Adding the edge $\{v,w\}$ to $E$ does not induce a cycle in contrast to the precondition that $G$ will have a cycle if you add any edge to it. Now we choose an arbitrary edge $\{u,v\}\in E$. If $(V,E\setminus\{u,v\})$ remains connected, then there exists a simple path from $u$ to $v$ which is a cycle in contrast to the precondition.
  • $(3)\implies (1)$: Based on the definition of a tree it suffices to show that $G$ has no cycles. Assume $G$ does contain a cycle one could remove one arbitrary edge without breaking the connectivity of the other vertices contrary to the assumption that $G$ won't be connected if any single edge is removed.

EDIT 1 based on the answer of Brian M. Scott.

(*1) Therefore two vertices $v,w\in V$ are connected by at least one path. Assume there is more than one path which connects $v$ and $w$ then $G$ would contain a cycle in constrast to the assumption that every tree has no cycles.

(*2) Therefore $G$ has no cycles. Assume that we can add an arbitrary edge $\{v,w\}$ without creating a cycle. By precondition however there already exists one unique single path from $v$ to $w$ and we would create a new cycle which is in constrast to the last assumption.

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

You need to do more for $(1)\implies(2)$: you’ve shown that any two vertices of $G$ must be connected by a path, but you’ve not shown that they are connected by a unique simple path. HINT: If $u$ and $v$ are connected by two simple paths, $G$ contains a cycle.

Your argument for $(2)\implies(4)$ is also incomplete: you still have to show that adding an edge to $G$ creates a simple cycle. HINT: If adding an edge $\{u,v\}$ does not create a simple cycle, could there have been a simple path from $u$ to $v$ in $G$?

share|improve this answer
    
I did work out extensions for both arguments based on your hints. Does the current version suffice now? –  Christian Ivicevic Oct 19 '12 at 20:09
    
@Christian: Looks good. Just one comment on the English: one unique path is redundant, since unique already implies one, and one unique single path is doubly redundant. Just say a unique path. –  Brian M. Scott Oct 19 '12 at 20:18
    
Ok I will keep that in mind. Thanks for now. –  Christian Ivicevic Oct 19 '12 at 20:19
1  
@Christian: Bitte sehr! –  Brian M. Scott Oct 19 '12 at 20:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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