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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityProblem 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?
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.