Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third:
- $G$ is connected
- $G$ is acyclic
- $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.
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?
This problem is from Chapter 3 of
Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley