# A connected acyclic graph has $n-1$ edges

Let $$G$$ be an undirected graph with $$n$$ nodes. Prove that any two of the following implies the third:

1. $$G$$ is connected
2. $$G$$ is acyclic
3. $$G$$ has $$n-1$$ edges

### Proving $$1, 2 \implies 3$$

A connected, acyclic graph is a tree. Each node(vertex), except the root, in the tree has exactly one edge going upwards(towards the root), hence it has $$n-1$$ edges.

### The Problem

I'm not able to write a formal proof for the other two. The problem is that here I used the fact that connected, acyclic graph is a tree and then it was easy to prove using properties of a tree, for the other I tried using contradiction but couldn't prove them.

Any hint on how to approach this problem and how to prove $$1, 2 \implies 3$$ without using the fact that connected acyclic graph is a tree?

### Reference

This problem is from Chapter 3 of Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley

Proving 2,3 implies 1: We have an acyclic graph $$G=(V, E)$$ with $$n-1$$ edges. We want to prove that $$G$$ is a connected graph. Assume for the sake of contradiction that $$G$$ is not connected. This means we have $$d>1$$ connected components, $$G=\{\bigcup_{i=1}^{d}G_i\}$$.
Since $$G$$ is acyclic, each connected component is a tree by definition. Let $$V_i$$ be the set of vertices of graph $$G_i$$. Then, the number of edges in $$G_i$$ is $$\mid E_i \mid = \mid V_i \mid - 1$$. Thus, the total number of edges in $$G$$ is $$\mid\ E \mid\ =\sum_{i=1}^{d}\mid E_i \mid =\sum_{i=1}^{d} (\mid V_i \mid-1)=\sum_{i=1}^{d}(\mid V_i \mid)- d = n - d < n -1$$.
The last inequality follows because $$d > 1$$. This is a contradiction that $$\mid\ E \mid\ = n-1$$.
Proving that 1,3 implies 2: We have a connected graph $$G=(V, E)$$ with with $$n-1$$ edges. We want to prove that $$G$$ is acyclic. I will not write the proof, but I will hint that (one of many possible proofs) you can use induction on the number of vertices. And let your assumption be that given $$G$$ with $$n-1$$ vertices and at most $$n-2$$ edges, then $$G$$ is acyclic.