2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Jon Noel Jun 25 '17 at 16:53
  • 1
    $\begingroup$ This problem can be found in L. Lovasz, Combinatorial Problems and Exercises, 10.1. $\endgroup$ – domotorp Jun 25 '17 at 21:11
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.