2004 IMO Shortlist Problems/C3

Problem

(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 $n \ge 4$ , find the least number of edges of a graph that can be obtained by repeated applications of this operation from a complete graph on $\displaystyle n$ 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 $\displaystyle n$ towns, where $n \ge 4$ . A road may be built between towns $\displaystyle A$ and $\displaystyle B$ if there exist two other towns $\displaystyle X$ and $\displaystyle Y$ such that there is no road between towns $\displaystyle A$ and $\displaystyle X$ ; there is no road between towns $\displaystyle X$ and $\displaystyle Y$ ; there is no road between towns $\displaystyle Y$ and $\displaystyle B$ . What is the maximum number of roads that can be built?

Solution

Surprisingly, the answer is $\displaystyle n$ .

We first claim that our graph must always stay connected. Indeed, if an edge $\displaystyle AB$ is removed, then it must have been part of a 4-cycle, so there must remain some other way of travelling from $\displaystyle A$ to $\displaystyle B$ . 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 $A_1\cdots A_n$ of odd length, and suppose that $A_1\cdots A_i B_1 \cdots B_{4-i}$ ( $2\le i \le 3$ ) is a 4-cycle. Since $\displaystyle i$ and $\displaystyle 4-i$ have the same parity, $A_1 B_{4-i} \cdots B_1 A_i \cdots A_n$ 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 $\displaystyle n$ vertices is $\displaystyle n-1$ , 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 $\displaystyle n$ edges. We will now describe recursively a sequence of moves that will lead to a graph with $\displaystyle n$ edges.

Suppose our graph has vertices $A_1, \ldots, A_n$ . For $\displaystyle n=4$ , we remove the edge $\displaystyle A_4A_1$ from the cycle $\displaystyle A_4A_1A_2A_3$ , and then remove the edge $\displaystyle A_4A_2$ from the cycle $\displaystyle A_4A_2A_1A_3$ . Since we have only 4 edges left, we cannot go further. Now, for $\displaystyle n>4$ vertices, for each positive integer $\displaystyle k< n-1$ , we remove the edge $\displaystyle A_nA_k$ from the 4-cycle $\displaystyle A_nA_kA_jA_{n-1}$ , where $\displaystyle A_j$ is some vertex other than $\displaystyle A_n, A_k, A_{n-1}$ . After this, $\displaystyle A_n$ will only be connected to $\displaystyle A_{n-1}$ . We then use our procedure for graphs of size $\displaystyle n-1$ on the subgraph $A_1 \cdots A_{n-1}$ to obtain a final graph with $\displaystyle n$ edges. Q.E.D.

Alternative

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.

Resources

Page

Toolbox

Search

2004 IMO Shortlist Problems/C3

Contents

Problem

Solution

Alternative

Resources