# Graphs: trees, induction proof

I was wondering if you could help me prove the following.

$G$ is a tree $\iff$ deleting any edge will disconnect it.

And a similar one:

$G$ is a tree $\iff$ adding any edge will create a cycle.

I know we should use the fact that if $G$ is a tree, then $G-v$ is also a tree for $v$ such that $deg(v)=1$.

I also know that any tree has at least two vertices whose degree is 1.

Could you help me with this?

Thank you.

-
Exactly what definition of tree are you using? –  Brian M. Scott Feb 6 '13 at 22:22
My definition of a tree (and therefore a basis for this proof) is that it is a connected graph with no cycles. –  Hagrid Feb 6 '13 at 22:26
In the second equivalence, you mean that you get a graph with exactly one cycle. Otherwise it's true for any connected graph. –  Louis Feb 6 '13 at 22:28
If you want every tree to have vertices of degree 1 I think you need to assume finiteness in addition to the definition you've just given. –  Shane O Rourke Feb 6 '13 at 22:29
Yes, you are right, I'd include the finiteness to the definition, but it's too late now, I'm afraid. And as for the second equivalence, I mean a single cycle. Could you help me with the first one? –  Hagrid Feb 6 '13 at 22:33

Here’s one approach. First prove that a graph with no cycle either has no edges or has a vertex of degree $1$. Thus, a non-trivial tree has a vertex of degree $1$, i.e., a leaf. Use this observation to prove by induction that a graph with $n$ vertices is a tree iff it has exactly $n-1$ edges and is connected. Then observe that adding an edge to a tree cannot disconnect it, so it must create a cycle (since the resulting graph has too many edges to be a tree). Similarly, removing an edge cannot create a cycle, so it must destroy ‘tree-ness’ by disconnecting the graph.

-
To reiterate my comment above, the graphs under consideration here are finite. (Otherwise you could have a 'straight graph' extending to infinity in both directions - every vertex in this graph has degree 2 and there are of course no cycles.) –  Shane O Rourke Feb 6 '13 at 22:48
@Shane: Finiteness is the default assumption. (Besides, I know the kinds of questions that the OP has been asking, so I’ve a good idea of the context.) –  Brian M. Scott Feb 6 '13 at 22:54

First claim is incorrect as stated. It should be

$G$ is a tree if and only if $G$ is connected and erasing any edge will disconnect it. (otherwise two disconnected trees are a counterexample for the converse)

$\Rightarrow$ is easy. $G$ is connected by the definition of the tree. Now assume by contradiction that erasing some edge $uv$ doesn't disconnect it. Then, there is a path $P$ between $u$ and $v$ in $G\backslash uv$, but then $P \cup \{ uv \}$ is a cycle in $G$ contradiction.

$\Leftarrow$: $G$ is connected. Assume now by contradiction that $G$ contains a cycle $C$. Then erasing some edge from the cycle doesn't disconect it, contradiction.

Second claim is also wrong.

$G$ is a tree if and only if $G$ has no cycles and adding any edge will create a cycle. (otherwise any connected graph satisfies the second condition)

$\Rightarrow$ $G$ has no cycles by the definition of the tree. Now, we prove that adding any new edge will create a cycle.

Let $uv$ be any edge not in $G$. Since $G$ is a tree, it is connected, and thus there is a path $P$ between $u$ and $v$. Then adding $uv$ creates the cycle $P \cup \{uv\}$.

$\Leftarrow$: $G$ has no cycle. We need to show that $G$ is connected.

Let $u,v$ be vertices in $G$. If $uv$ is an edge we are done, otherwise, adding $uv$ will create a cycle $C$ which of course contains $uv$ as an edge. Erasing now $uv$ from this cycle, we are left with a path connecting $u$ and $v$.

-

Both of your statements follow from the fact that $G$ is a tree iff for any two vertices, there is exactly one simple path between them. To see this, observe that it's true of one-vertex "empty" trees and preserved if you add or remove a leaf.

-
Could you explain it a bit further? I think that for the second equivalence I could say that if there was any cycle in $G$ it would have to be in $G-v$, too, because $deg(v)=1$, and from induction hypothesis there is no cycle in $G-v$. My problem with the first equiv. is that I don't know how to use the fact that $G$ is the minimal connected graph. Does it suffice to say that if $G-v$ was a minimal connected graph, then adding an egde ... (and I don't know what to do now). –  Hagrid Feb 6 '13 at 22:27
Following my approach: Let $ij$ be an edge. According to the fact I mentioned, there is only one way to get from $i$ to $j$ in $G$: across $ij$. Taking it out means that there is no path from $i$ to $j$, so $G\setminus ij$ is disconnected. –  Louis Feb 6 '13 at 22:32
It's that simple? Thanks a lot. –  Hagrid Feb 6 '13 at 22:35