Find the maximum number such that the following holds: there is an edge-colored graph with 60 vertices and edges, with each edge colored either red or blue, such that in that coloring, there is no monochromatic cycles of length 3 and no monochromatic cycles of length 5.

Solution:

First, I shall show that this graph cannot contain a . This is hard to explain without a picture (and frankly requires a bit more casework than I am willing to explain) but this is not so hard to prove.

Now, by Turan's theorem the maximum number of edges in this graph is .

I shall construct such a graph with edges. Partition the vertices into four groups of vertices and call these groups . Connect every two vertices in differing groups but connect no two vertices in the same group (this is a ). Clearly this graph has edges. Color every edge between groups and red and color every edge between groups and red as well. Color all other edges blue. It is clear that this graph has no monochromatic cycles of odd length, so we are done.

The motivation for these steps is not difficult to find. When considering problems that ask about the maximum number of edges, Turan should be the first thing one tries. Then the step follows easily because one needs a lack of some complete graph. The -partite graph itself is the unique equality case in Turan, and the coloring is clear after some small cases.