1
$\begingroup$

I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.

$\endgroup$
  • $\begingroup$ "that goes beyond proof by strong induction". It looks like your tree might have been defined recursively as a rooted tree. Another definition of a tree is acyclic connected graph. A common proof is then simple induction by removing one leave at a time. $\endgroup$ – Apass.Jack Dec 1 '18 at 17:46
2
$\begingroup$

You can see a (binary) tree as a directed graph: suppose the root is the "lowest" node and the leaves are the "highest" ones, then say that all the edges are oriented upwards. Then, every node that is not the root will have exactly one edge entering in it, and every edge will be pointing at exactly one node. This means that if you have $n$ nodes, you have to have $n-1$ edges (one per node with the exception of the root).

$\endgroup$
1
$\begingroup$

This is essentially a different perspective on OmG's answer.

The technical rendition is: A tree is contractible (i.e. homotopic to a point). Since the Euler characteristic (the number of vertices minus the number of edges) is a homotopy invariant, any tree has the same Euler characteristic as a point which is $1$ (one vertex minus zero edges).

The non-technical rendition is: If we collapse a leaf into its parent, we lose one edge and one node, so the difference between the number of edges and the number of vertices remains the same. Clearly, we can just keep doing this until we're left with only the root node for which the difference between vertices and edges is $1$ (one vertex and zero edges).

More generally, collapsing two distinct vertices along an edge that joins them is a homotopy, so for any graph at all we could collapse any distinct pair of vertices joined by an edge without changing the Euler characteristic. That means in the above we didn't need to work from leaves to root; we could have collapsed any edge, though that would have led to intermediates that aren't binary trees. It also means that since a loop (one vertex and one edge from that vertex to itself) has Euler characteristic $0$, then any cycle has Euler characteristic $0$.

$\endgroup$
0
$\begingroup$

The intuition is "as the binary tree is a tree and it has a connected component without any isolate node, and we know in a tree $|E| = |V| - 1$, hence the number of edges of the binary tree with the $n$ node is $n - 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.