Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

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

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