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.

How would I start going about proving these properties?

Prove that the following three properties of a CONNECTED graph $G$ are equivalent:

  1. $G$ has no cycles.

  2. $G$ is a graph on $N$ vertices with $N-1$ edges.

  3. Removing an edge from $G$ disconnects the graph.

I understand that if you remove an edge from a graph that has no cycles, it will disconnect a node.

share|improve this question
    
You want to show that 3 properties are equivalent, so a good way to do that would be to prove a cycle of implications: (1) => (2) => (3) => (1). Hint: (3) => (1) is pretty easy, the other two may be a little trickier (depending on what results you have already proved). –  Ted Sep 19 '11 at 6:36
2  
BTW, these properties define a tree. –  lhf Sep 19 '11 at 11:04
add comment

2 Answers

up vote 3 down vote accepted

Ted's comment is correct, of course, but this is not always the easiest way to prove such an equivalence. I would just try to figure out which implications you can actually prove and hope that this is enough. (3)$\Rightarrow$(1) is indeed easy, and so is (1)$\Rightarrow$(3).

(2)$\Rightarrow$(3) is pretty clear as well. So now you know that (1) and (3) are equivalent and that (2) implies both of these properties.

It remains to show that (1) and (3) together imply (2). (Actually, you will only have to use (1).) I would suggest to go by induction on the number of vertices. If there are no cycles and the graph has at least 1 vertex, then there is a vertex of degree 1 (why?). Remove that and observe that the smaller graph that you obtain is connected and has no cycles.


Edit: I noticed that I contradicted myself somewhat: Clearly, I am actually providing hints to prove (1)$\Rightarrow$(2)$\Rightarrow$(3)$\Rightarrow$(1). But I still believe that a good strategy to prove the equivalence of more than two statements is to see which implications look easiest and then hope that you get enough for the equivalence.

Edit 2: For the implication (2)$\Rightarrow$(3) you should also use induction. If the graph has no more than $n-1$ edges, there must be a vertex of degree $\leq 1$. Since the graph is connected, that vertex has degree exactly $1$. Remove that vertex and adjacent edge and use the inductive hypothesis on the smaller graph. The base case is a two vertex graph joined by an edge.

share|improve this answer
add comment

If T is a tree (connected graph, no circuits) other than the one with a single vertex then T has at least two 1-valent (degree 1) vertices. (Pick any vertex and look for the valence of a vertex which is as "far away" as possible from it.) Now one can show that if a tree has n vertices it has n-1 edges. This is also a useful lemma for showing Euler's formula for connected graphs: V + F - E = 2 (where the unbounded region counts as one face, so for trees, F is 1).

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