Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A computer network has machines, and some pairs are joined by cables, at most one cable per pair. The engineer wants to be sure the network is connected, so that every machine can reach every other one through cables, without checking the layout.
Find the largest number of cables a network of machines can have while still not being connected. Prove that every network with one more cable is connected. Describe a network that reaches the largest number.
The degrees add up to twice the number of edges, so the number of odd vertices is even. has edges. A simple graph on vertices with more than edges is connected.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. The split. If the network is not connected, take one component with machines, . No cable joins it to the other machines.
Step 2. The most cables. At most cables. This is largest at the ends, or , where it equals . For it is , and it keeps falling towards , where it is .
Step 3. The example. Join every two of machines and leave the tenth alone: cables and not connected.
Step 4. One more cable. A network with cables cannot be split, because every split allows at most . So it is connected.
Answer: at most cables without being connected, so cables always make it connected. Proof complete.
Log in to join the discussion.
Loading…