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

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

• If this is self-study, please add an appropriate tag and above all indicate your work on the problem so far. If this is not self-study, then I don't think we have here a coherent question.
– Nick Cox
Jul 29, 2013 at 0:50
• I don't see why this should be tagged (machine-learning). Jul 29, 2013 at 10:41
• If a graph with $n$ vertices and $n$ edges there must a circle? Jul 29, 2013 at 10:44
• Complete graph: bit.ly/1aUiLIn Jan 25, 2014 at 7:47

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.

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....

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?

A tree is by definition a connected (hence non empty) graph $G$ without cycles. Here is a proof by induction of the number$~m$ of edges that every such (finite) tree has $m+1$ nodes. (Then of course every tree with $n$ nodes has $n-1$ edges). If $m=0$ (no edges) one cannot have more than $1$ nodes (connectivity) and no less either (non-emptyness). In the case $m>0$ choose any edge $(a,b)$. If there were a path from $a$ to $b$ without using that edge, then one would have a cycle in $G$ together with that edge. Therefore removing the edge $(a,b)$ disconnects $a$ from $b$ in the remaining graph $G'$. Also every node is connected in $G'$ either to $a$ or to $b$ (every path in $G$ passing neither through $a$ nor $b$ remains a path in $G'$). So $G'$ is a disjoint union of two trees; say they have $p,q$ edges respectively. Then $m=p+q+1$, and by induction $G'$ (hence $G$) has $(p+1)+(q+1)=p+q+2=m+1$ nodes.

For any finite graph the sum of the degrees of the nodes is twice the number of edges. For a tree with $n$ nodes and $n-1$ edges it follows that all nodes cannot have degree${}\geq2$. In fact either there are at least two nodes of degree$~1$ (leaves) or one of degree$~0$; the latter only occurs for $n=1$. In the proof above I wanted to avoid using this fact in passing, as its direct proof is about a difficult as the above proof itself.

Hint: Check $n=1,2,3,4$ and see which ones you can rule out...

• Why the downvote? Jan 27, 2015 at 16:11

Here is the Graphical Intuition Since in a tree, every node is connected by exactly 1 new edge, to its parent (so we'd have $n$ edges total); but this is true except for the first ("root") node who doesn't have a parent, so it doesn't have an edge to its parent so that's $n-1$ total edges.

You can also think of every node having exactly $2$ edges, being connected to parent and child, but these edges would overlap since they are all mutual so that will be $N$ edges again; and here we again have to exclude the root node which has no parent, so total $N-1$ edges.