A connected acyclic graph has $n-1$ edges

Question

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

Answer 1

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.