# Prove equivalence of conditions for a tree

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.

-

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$?

-
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
@Christian: Bitte sehr! –  Brian M. Scott Oct 19 '12 at 20:20