Prove that to fully connect $n$ nodes we need at least $n-1$ pairwise links Suppose we have $n$ points/nodes, and we are given $m$ pairwise links/edges that we can use to connect arbitrary pairs of nodes.
Our goal is to arrange the edges in order to fully connect the nodes, that is, to have a configuration such that one can go from any node to any other node passing through the edges.
For example, for $n=4$ and $m=3$, denoting with $(ij)$ an edge between $i$-th and $j$-th node, such fully connected networks could be $(12)(23)(34)$, or $(12)(13)(14)$.
By trying this in a few cases, it seems clear that the smallest $m$ for which this is possible is $m=n-1$. What's a good way to prove that this is indeed the case?
 A: Hi you can easily prove it by induction.
Base case: $n=2$. You need $n-1=1$ edges. Graph connected.
Assume it is true that for $n$ nodes you need $n-1$ edges.
Now add a node, hence $n+1$ nodes. Just connect the last node to another node, and the number of edges become $n$.
A: First create a single link between two nodes. As all the nodes are to be connected, the network of links must be connected. Adding a new link to the existing network further connects at most $1$ new node, and we have $n-2$ nodes to add, hence $n-1$ links.
A: Assume $n \ge 2$. Let $(i, j)$ be an edge, with $i\not = j$. Simplify the graph by removing that edge and identifying the vertices $i$ and $j$. The new graph has one less egde and one less vertex. Hence the difference between the number of edges and the number of vertices remains the same. By induction, this difference must be $\ge -1$.
A: Define the connected components of a set of nodes and links (a graph) to be the maximal subsets of the nodes which are connected each other by paths. That is, two nodes are in the same component if they are joined by a path, and in different components otherwise.

*

*If there are no links, then no node can reach any other, so there are $n$ connected components.


*If a graph currently has $k$ connected components, and you add a single link to the graph, then the new graph has at least $k-1$ connected components. This is because, at best, the new link can join to components together, replacing those two with one and decreasing the over all number by $1$.
These two facts allow you to prove the following by induction: a graph with $n$ nodes and $m$ edges will have at least $n-m$ connected components. Therefore, if there are only $n-2$ links, there will be at least two connected components, so the graph is not connected.
