# Properties of Connected Graphs

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.

• 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
Commented Sep 19, 2011 at 6:36
• BTW, these properties define a tree.
– lhf
Commented Sep 19, 2011 at 11:04

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