Exercise 4.8.3

When a graph is connected, it means for any two nodes, we can find a path, that connects the pair of nodes.

To connect $N$ nodes, we need at least $N-1$ edges to span all the nodes, so we have $M\ge N-1$.

For any given node, if we count the unique edges of all paths from it to all the other nodes. Since in connected graph, the node is connected to all other nodes, the lengths of paths have to range from 1 to $N-1$. And the maximum length has to be $N-1$, if it’s larger than $N-1$ you have a cycle.

Let $l(i,j)$ be the maximum length of unique edges from node $i$ to $j$, then the maximum of $l(i,j)$ among all $i,j$ has to be $N-1$, suppose node $p,q$ has the maximum length $N-1$. We claim that $M\le N-1$. Otherwise, there must exist an edge $k$, that is not on the path from $p$ to $q$, meaning exists nodes not on the path of $p\to q$. Since the length between $p,q$ is $N-1$, there are already $N$ nodes, this contradicts with extra nodes coming from edge $k$. So we have $M\le N-1$.

We then conclude that $M=N-1$.