IMO 2004 SL C3

Origin: AUS | Category: Combinatorics

Problem

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 \geq4, find the least number of edges of a graph that can be obtained by repeated ap- plications of this operation from the complete graph on n vertices (where each pair of vertices are joined by an edge).

Solution

The least number of edges of such a graph is n. We note that deleting edge AB of a 4-cycle ABCD from a connected and nonbipartite graph G yields a connected and nonbipartite graph, say H. Indeed, the connectedness is obvious; also, if H were bipartite with partition of the set of vertices into P1 and P2, then w.l.o.g. A, C \inP1 and B, D \inP2, so G = H \cup{AB} would also be bipartite with the same partition, a contradiction. Any graph that can be obtained from the complete n-graph in the de- scribed way is connected and has at least one cycle (otherwise it would be bipartite); hence it must have at least n edges. Now consider a complete graph with vertices V1, V2, . . . , Vn. Let us remove every edge ViVj with 3 \leqi < j < n from the cycle V2ViVjVn. Then for i = 3, . . . , n −1 we remove edges V2Vi and ViVn from the cycles V1ViV2Vn and V1ViVnV2 respectively, thus obtaining a graph with exactly n edges: V1Vi (i = 2, . . . , n) and V2Vn.