Given a positive integer number , determine the maximum number of edges a simple graph on vertices may have in order that it contain no cycles of even length.
Solution
The required maximum is . It is achieved, for instance, by an arm wind-mill if is odd, and an arm wind-mill with an extra edge joined at the hub if is even.
To show that a simple graph on vertices with no cycles of even length has at most edges, let be one such with a maximal edge-set . By maximality, is connected. Let be a spanning tree (that is, a maximal connected acyclic subgraph) of , and let denote the edge-set of ; it is well-known that . The end-points of any edge in are joined by a unique simple path in . Since is acyclic, if and are distinct edges in , then the edges the corresponding paths in , and , may share a path; and since has no cycles of even length, the paths and are actually edge-disjoint — otherwise, at least one of the cycles and (mod 2) would have an even length. It follows that the total length of the cycles , does not exceed . There are such cycles, each of length at least 3, so ; that is, .