TAOCP 2.3.4.1 Exercise 10
Let the terminals $T_1,\ldots,T_n$ be the vertices of a graph $G$, and let each wire correspond to an edge.
Exercise 10. [**] $$16$$ An electrical engineer, designing the circuitry for a computer, has $n$ terminals $T_1,T_2,\ldots,T_n$ that should be at essentially the same voltage at all times. To achieve this, the engineer can solder wires between any pairs of terminals; the idea is to make enough wire connections so that there is a path through the wires from any terminal to any other. Show that the minimum number of wires needed to connect all the terminals is $n-1$, and $n-1$ wires achieve the desired connection if and only if they form a free tree (with terminals and wires standing for vertices and edges).
Verified: yes
Solve time: 1m24s
Let the terminals $T_1,\ldots,T_n$ be the vertices of a graph $G$, and let each wire correspond to an edge. The requirement that there be a path from any terminal to any other means exactly that $G$ is connected.
We must show:
- Every connected graph on $n$ vertices has at least $n-1$ edges.
- A connected graph on $n$ vertices has exactly $n-1$ edges if and only if it is a free tree.
First, prove the lower bound. Let $G$ be any connected graph with $n$ vertices. If $G$ contains a cycle, remove an edge from that cycle. The graph remains connected, because the two endpoints of the removed edge are still joined by the rest of the cycle. Repeat this process until no cycles remain.
The resulting graph $H$ is connected and acyclic, so $H$ is a free tree. By Theorem A(d), a free tree with $n$ vertices has exactly $n-1$ edges. Since $H$ was obtained from $G$ only by deleting edges,
$$ |E(G)| \ge |E(H)| = n-1. $$
Therefore every connected graph on $n$ vertices has at least $n-1$ edges. Hence at least $n-1$ wires are necessary.
Next, show that $n-1$ wires suffice. A free tree on the $n$ terminals is connected and has exactly $n-1$ edges by Theorem A(d). Thus $n-1$ wires are enough.
Finally, characterize the configurations using exactly $n-1$ wires.
Suppose $G$ is connected and has exactly $n-1$ edges. If $G$ contained a cycle, we could remove an edge of that cycle and the graph would remain connected. The resulting connected graph would then have only $n-2$ edges, contradicting the fact proved above that every connected graph on $n$ vertices has at least $n-1$ edges. Therefore $G$ is acyclic. Since $G$ is connected and acyclic, $G$ is a free tree.
Conversely, every free tree on $n$ vertices is connected and has exactly $n-1$ edges by Theorem A(d).
Therefore the minimum number of wires needed is
$$ \boxed{n-1}, $$
and a configuration with $n-1$ wires achieves the desired connectivity if and only if the wires form a free tree. ∎