[Math] Properties of Connected Graphs

graph theoryproof-writing

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.

Best Answer

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.