15
$\begingroup$

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

$\endgroup$
4

6 Answers 6

23
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Why the downvote? $\endgroup$
    – tomasz
    Jan 27, 2015 at 16:11
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .