Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)

Question

The question is in the title. I can see why the bound is sharp (for example, a lot of triangles sharing one common vertex if n is odd, or the same but with one spare edge hanging out if n is even). But I can't prove why the bound is the best possible.

I know that each edge must belong to at most one cycle. I was thinking that you could take any path or odd big odd cycle and turn it into bunch of triangles wherever possible, but I think that might not be valid because a lot of greedy local optimums isn't necessarily the global optimum. So what do I do?

I tried looking online for an answer before posting this and all I could find is this: Link Is the reasoning faulty there? I couldn’t make sense of it after it talked about decomposing into cycles.

Thanks for any help

Answer 1

This is not true if graph is not simple, for example take a single vertex and a loop, there is one edge, but your bound equals zero.

On the other hand, if the graph in question is simple then here are some hints:

• WLOG you can assume that your graph is a single connected component.
• Take some spanning tree of it, you will have $n-1$ edges there.
• You are left with more than $\lfloor \frac{n-1}{2} \rfloor$ edges, but observe that you cannot add any vertices (the spanning tree touches all of them), therefore, any edge you add will produce a cycle (at least one).
• No edge can be shared among cycles, as this would create an even cycle (this means that each edge you add will create a cycle, but it mustn't create two or more).
• The best you can do is form triangles (the smallest possible odd cycles), but you can't obtain more than $\lfloor\frac{n-1}{2}\rfloor$ (for any of the remaining edges you need two from the spanning tree), which is why you can't add yet more edges.

I hope it helps ;-)