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.

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.

share|improve this question
2  
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
2  
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

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
1  
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

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.

share|improve this answer
    
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
1  
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

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

share|improve this answer

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.