2004 IMO Shortlist Problems/C3
(Australia) The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer , find the least number of edges of a graph that can be obtained by repeated applications of this operation from a complete graph on vertices (where each pair of vertices are joined by an edge).
This was also Problem 2 of the 2005 Colombia TST.
The proposer's formulation is:
In a certain country there are towns, where . A road may be built between towns and if there exist two other towns and such that there is no road between towns and ; there is no road between towns and ; there is no road between towns and . What is the maximum number of roads that can be built?
Surprisingly, the answer is .
We first claim that our graph must always stay connected. Indeed, if an edge is removed, then it must have been part of a 4-cycle, so there must remain some other way of travelling from to . Hence the graph must always stay connected.
We next claim that there is always some cycle of odd length. This is certainly true initially, for there are triangles initially. Now, suppose that we have a cycle of odd length, and suppose that () is a 4-cycle. Since and have the same parity, is a cycle of odd length. But we cannot disrupt both this cycle and the original cycle by removing only one edge from our 4-cycle. Thus after each step, there must remain at least one cycle of odd length.
The minimal number of edges in a connected graph with vertices is , as each vertex apart from some special initial vertex needs at least one edge linking it indirectly to the initial vertex. Such minimal connected graphs must always be trees, for if there is a cycle, then we can remove one edge while keeping the graph connected. Since our graph must always be connected and must always have at least one cycle, it must always have at least edges. We will now describe recursively a sequence of moves that will lead to a graph with edges.
Suppose our graph has vertices . For , we remove the edge from the cycle , and then remove the edge from the cycle . Since we have only 4 edges left, we cannot go further. Now, for vertices, for each positive integer , we remove the edge from the 4-cycle , where is some vertex other than . After this, will only be connected to . We then use our procedure for graphs of size on the subgraph to obtain a final graph with edges. Q.E.D.
It is also possible to prove that our final graph cannot be a tree by noting that trees are bipartite. But if we reconstruct our original graph by completing 4-cycles, the graph will remain bipartite, a contradiction.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.