Maths Olympiad Prep

Library / /16 of 70

Combinatorics Difficulty 8.0 National Olympiad, round 2 Prove it Romania

Given a positive integer number nn, determine the maximum number of edges a simple graph on nn vertices may have in order that it contain no cycles of even length.

Solution

The required maximum is 3(n1)/2\lfloor 3(n-1)/2 \rfloor. It is achieved, for instance, by an (n1)/2(n-1)/2 arm wind-mill if nn is odd, and an (n2)/2(n-2)/2 arm wind-mill with an extra edge joined at the hub if nn is even.

To show that a simple graph on nn vertices with no cycles of even length has at most 3(n1)/23(n-1)/2 edges, let GG be one such with a maximal edge-set EE. By maximality, GG is connected. Let TT be a spanning tree (that is, a maximal connected acyclic subgraph) of GG, and let EE' denote the edge-set of TT; it is well-known that E=n1|E'| = n-1. The end-points of any edge ee in EEE \setminus E' are joined by a unique simple path α\alpha in TT. Since TT is acyclic, if ee and ee' are distinct edges in EEE \setminus E', then the edges the corresponding paths in TT, α\alpha and α\alpha', may share a path; and since GG has no cycles of even length, the paths α\alpha and α\alpha' are actually edge-disjoint — otherwise, at least one of the cycles α+e,α+e\alpha + e, \alpha' + e' and α+e+α+e\alpha + e + \alpha' + e' (mod 2) would have an even length. It follows that the total length of the cycles α+e,eEE\alpha + e, e \in E \setminus E', does not exceed E|E|. There are EE=EE=En+1|E \setminus E'| = |E| - |E'| = |E| - n + 1 such cycles, each of length at least 3, so 3(En+1)E3(|E| - n + 1) \le |E|; that is, E3(n1)/2|E| \le 3(n-1)/2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.