Q:

How many edges does an undirected tree with $n$ nodes have?

How many edges does an undirected tree with $n$ nodes have?

A:

This is a very standard fact; any basic text will tell you that an undirected tree with $n$ nodes must have exactly $n-1$ edges. You can prove this by induction on $n$. Clearly a tree with one node has no edges. Suppose that every tree with $n$ nodes has $n-1$ edges, and let $T$ be a tree with $n+1$ nodes. $T$ must have a leaf, i.e., a node $v$ such that $\deg v=1$. (If not, $T$ would contain a circuit: why?) Remove $v$ and the one edge incident at $v$. What’s left is still a tree (why?), and it has only $n$ vertices, so it has $n-1$ edges. Thus, $T$ must have had $(n-1)+1=n$ edges.

A:

Here is a simple intuitive proof I first saw in a book by Andy Liu:
Imagine the tree being made by beads and strings. Pick one bead between your fingers, and let it hang down.
Since the tree is connected, it all hangs in one piece. And because it has no cycles, each bead lies at the end of one string, and for each string there is a bead at the end. Thus, you can pair each string with exactly one bead: the bead at the end.
This means there are as many strings as the beads you can see. As there is a hidden bead, the number of beads is 1 more than the number of strings....

A:

HINT: Suppose we have an undirected tree T (a loop-free connected undirected graph that contains no cycles) with N vectices (nodes).  If T has N or more edges, then there must exist a cycle contradicting that T is a tree.
Why is this?

