# The maximum number of edges in an even-cycle-free graph with $n$ vertices

Problem Given any positive integer $n$, what is the maximum number of edges in an even-cycle-free graph with $n$ vertices?

Is the above problem an unsolved problem in extremal graph theory? Are there any results about this problem?

• Tony's argument below should answer your question. It's also worth mentioning that the problem of maximizing the number of edges in a graph forbidding an even cycle of fixed length is well studied (see, e.g., the Bondy-Simonovits Theorem). – Jon Noel Jun 25 '17 at 16:53
• This problem can be found in L. Lovasz, Combinatorial Problems and Exercises, 10.1. – domotorp Jun 25 '17 at 21:11

The answer is $\lfloor \frac{3}{2}(n-1)\rfloor$. First note that if $G$ is $2$-connected and even-cycle-free, then $G$ must just be an odd cycle. To see this, consider an ear-decomposition of $G$. If $G$ is not just a cycle, then $G$ contains a cycle and an ear. However, by parity considerations, a cycle and an ear always contains an even cycle.
Now let $G$ be an arbitrary even-cycle-free graph and consider its block-cut-tree $T$. By the previous remark, each block of $G$ is an odd cycle or just an edge. To maximize the number of edges, each block of $G$ should be a triangle. Thus, the maximum number of edges is attained by a 'tree of $k$ triangles.' This graph has $3k$ edges and $2k+1$ vertices. For $n$ even (say $n=2k+2$), the maximum is attained when $T$ has exactly $k$ blocks which are triangles and exactly one block which is an edge. This is a complete characterization of the extremal examples.