2004 IMO Shortlist Problems/C3
Contents
[hide]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 , 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?
Solution
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.
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.