Exercise 4.8.4

If a graph is connected with $N$ nodes and $N-1$ edges, then we know that is a spanning tree. We can use similar argument from problem IV.8.3, or as below.

We can show this like below. We first start with any two ‘one-line-cluster’s, where we start with any node, e.g. $x_1$, since there always is a path between $x_1$ and all other nodes, there must be a node that’s directly connected with $x_1$, label this $x_2$, do this continuously until $x_i$, where none of the rest points directly connects with $x_i$. This will be a ’one-line=cluster’, with $i-1$ edges. For a connected graph, the minimum number of nodes in a ‘one-line-cluster’ is 2.

Suppose we have another ‘one-line-cluster’ with $j$ nodes, so its number of edges is $j-1$.

Now we claim that if these two clusters compose a connected graph, there has to be $i+j-1$ edges, i.e. only 1 edge connected from cluster $i$ to $j$. If there are more than 1 intra-cluster edge, then we can easily see that a cycle is formed.

So for any ‘one-line-cluster’ of size $K$, we have $K-1$ edges.

So for a connected graph, we start with any two ‘one-line-cluster’ and form a larger cluster, gradually adding ‘one-line-cluster’ one-by-one, we see that the final number of edges should be $N-1$.