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?

Improve this question
$\endgroup$
2
  • 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
    Commented Jun 25, 2017 at 16:53
  • 1
    $\begingroup$ This problem can be found in L. Lovasz, Combinatorial Problems and Exercises, 10.1. $\endgroup$
    – domotorp
    Commented Jun 25, 2017 at 21:11

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .