I am too lazy to post a full solution so I will post a general outline: (1) First prove that the graph cannot contain a complete graph on 5 vertices... this is quite easy with some simple casework. (2) Use Turan's Theorem to determine that the maximum number of edges is 1350 (3) To construct such a graph, split up the vertices into 4 groups of 15 each. Call them groups 1, 2, 3, 4 respectively. Connect every two vertices in different groups by an edge, for every two vertices in the same group, do not connect them (this is a complete 4-partite graph). Now color every edge between groups 1 and 2 blue. Do the same for groups 2 and 3, and groups 3 and 4, and groups 4 and 1. Color every edge between groups 1 and 3 red, and color every edge between groups 2 and 4 red. It is easy to see that the resulting graph has no monochromatic cycles of odd length, and that it has 1350 edges, which provides the desired construction. 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 step 1 follows easily because one needs a lack of some complete graph. The graph itself from step 2 is the unique equality case in Turan, and the coloring is clear after some small cases.

For a general graph $G$ and vertex $v$ in $G$, we can "clone" $v$ to obtain a new graph $G'$ by adding a new vertex $v'$ with edges such that for each $u \in V(G)$, $v \sim u \Leftrightarrow v' \sim u$ (and $v$ and $v'$ are not neighbors) and such that if $vu \in E(G)$ then $v'u$ matches it in color. We will use cloning to recursively generate graphs witnessing the maximum. Also for general graphs on $n$ vertices, let the set of graphs satisfying the property be $P_n$ and let the desired maximum number of edges be $m(n)$. Then we have the following two lemmas: $\textbf{Lemma 1}$: $m(r) \le \left\lfloor \frac{r \cdot m(r-1)}{r-2} \right\rfloor$. Proof: For an arbitrary $G \in P_r$ with $m(r)$ edges, each subgraph $H$ induced by a subset of $r-1$ vertices of $G$ must be in $P_{r-1}$ and have at most $m(r-1)$ edges. Adding over all $\binom{r}{r-1}$ subsets of $r-1$ vertices, we count each edge in $\binom{r-2}{r-3}$ subsets so $m(r) \le \frac{m(r-1)\binom{r}{r-1}}{\binom{r-2}{r-3}} \Rightarrow m(r) \le \left\lfloor \frac{r m(r-1)}{r-2}\right\rfloor$. $\square$ $\textbf{Lemma 2}$: For $G \in P_{k}$, the graph $G'$ obtained by cloning any vertex of $G$ is contained in $P_{k+1}$. Proof: Let the cloned vertex be $v'$. If $G' \not \in P_{k+1}$, then the monochromatic cycle must include $v'$. If $v'$ forms a monochromatic $3$-cycle or $5$-cycle not containing $v$, then it is of the form $v'a_1 a_2 \cdots$. Since $v'$ is a clone of $v$, $v$ would also form a monochromatic $3$- or $5$-cycle as $va_1a_2 \cdots$, a contradiction. If $v'$ forms a monochromatic $5$-cycle containing $v$, then it is of the form $av'bvc$ (since $v$ and $v'$ are not adjacent) WLOG in red. Since $vc$ is a red edge in $G'$, $v'c$ is also a red edge in $G'$ so $a, c, v'$ form a red $3$-cycle, which has already been ruled out, a contradiction. $\square$ We will prove, by induction, that $m(4n) = 6n^2$ for each $n \in \mathbb{N}$, so that $m(60) = 1350$. As a base case, $m(4) \le \binom{4}{2} = 6$, which is achievable: label the vertices $v_1,v_2,v_3, v_4$ and color $v_1v_2, v_2v_3, v_3v_4, v_4v_1$ all in red and $v_1v_3$, $v_2v_4$ in blue. Now assume $m(4n) = 6n^2$ for some $n \ge 1$. From lemma $1$ applied four times in succession, $m(4n+1) \le 6n^2+3n, m(4n+2) \le 6n^2+6n+1, m(4n+3) \le 6n^2+9n+3$, and $m(4n+4) \le 6n^2+12n+6 = 6(n+1)^2$. To show that these values are attainable, we successively (and greedily) clone a vertex of largest degree. For $G_{4n} \in P_{4n}$ with $6n^2$ edges, some vertex has degree at least $\left\lceil\frac{12n^2}{4n}\right\rceil = 3n$. Cloning this vertex and using lemma $2$, we add $3n$ edges to obtain $G_{4n+1} \in P_{4n+1}$ with $6n^2+3n$ edges. Applying the pigeonhole principle and lemma $2$ three more times, we get a graph $G_{4n+4} \in P_{4n+4}$ with $6(n+1)^2$ edges so $m(4n+4) = 6(n+1)^2$. (Notice that this also shows that $m(4n+1) = 6n^2+3n, m(4n+2) = 6n^2+6n+1, m(4n+3) = 6n^2+9n+3$ for all $n$.)

It is not hard to show that any $K_5$ has either a monochromatic three or five cycle. Thus, our graph cannot have any 5-cliques, so by Turan's theorem, it has at most $(1-1/4)\cdot 60^2/2=1350$ edges, and we claim the bound is sharp. Consider a complete 4-partite graph. We see that it has $\binom{4}{2}\cdot 15^2 = 1350$. Let the groups be $A,B,C,D$. Color all edges from $A$ to $B$, $A$ to $C$, and $B$ to $C$ blue, and all others red. It is easy to see that this works.

yayups wrote: Let the groups be $A,B,C,D$. Color all edges from $A$ to $B$, $A$ to $C$, and $B$ to $C$ blue, and all others red. It is easy to see that this works. This is of course wrong since taking a vertex from each of groups $A,B,C$ will give a monochromatic blue triangle.But the construction can be modified to become correct.Consider a 4-partite graph as above with each part containing $15$ vertices let the groups be $A,B,C,D$ color all edges from $A$ to $B$ and $B$ to $C$ and $C$ to $D$ and $D$ to $A$ blue and the rest red.

Solved with goodbear and Th3Numb3rThr33. The answer is $1350$. To achieve this, partition the vertex set into $A$, $B$, $C$, $D$ of $15$ vertices each; draw an red edge between any two vertices belonging to $(A,B)$, $(B,C)$, $(C,D)$, $(D,A)$, and blue between vertices belonging to $(A,C)$, $(B,D)$. For maximality, it is not hard to check there is no $K_5$, so by Turan's theorem, \[E\le\left(1-\frac14\right)\frac{n^2}2=1350,\]as desired.

Remark: WwwoooowwW. Nice problem! First, we show the graph on $60$ vertices and $E$ edges must not contain a $K_5$. Claim: If we were to color all $10$ edges of $K_5$ with red and blue, we can find either a triangle or a $5$-cycle (not entirely obvious). Proof: We show that if there are no monochromatic triangles, then there is a monochromatic $5$-cycle. It suffices to show the contrapositive: if there is no monochromatic $5$-cycle, then there is a monochromatic triangle. Note that if there is no monochromatic $5$-cycle, then all cycles must have length $4$, or else we would have a monochromatic triangle, then done. Label the vertices as $1, 2, 3, 4, 5$. We consider the five $4$-cycles $1234, 2345, 3451, 4512, 5123$. Suppose that $k$ of these cycles are red and $5-k$ of these cycles are blue. WLOG $k \geq 3$. Suppose $1234$ is red. Then, if either one of $1245$ or $1345$ are red, then we are done. If $k = 4, 5$ we are done. Let's consider $k = 3$. We are left with only one option: $1234, 1245, 1345$ red, and $2345, 1235$ blue. Then, there exists a blue triangle, and we are done. $\square$ So if the graph on $E$ edges has a $K_5$, then a monochromatic triangle or $5$-cycle must exist, impossible. Hence there is no $K_5$, as desired. We derive an upper bound with Turan's theorem, giving a maximum of\[E \leq \left(1 - \frac{1}{4}\right) \cdot \frac{60^2}{2} = 1350\]edges. It remains to find a working construction. Let us partition the $60$ vertices into four groups $A, B, C, D$. Suppose we draw red edges between $(A, B), (B, C), (C, D), (D, A)$ and blue ones between $(A, C), (B, D)$. This does indeed give a total of $15^2 \cdot 6 = 1350$ edges, and a quick check shows that this does indeed have no triangles or $5$-cycles. We are done! $\blacksquare$

It is not hard to show that there cannot be any $K_5$, each edge being either red or blue. (Basically, all graphs on 5 vertices with no monochromatic triangles are a star with a monochromatic cycle on the outside, breaking the 5-cycle condition.) Therefore, by Turan's Theorem, the number of edges is at most \[ E \le \left(1-\frac14 \right) \cdot \frac{60^2}{2} = 1350. \]Equality is achieved by using a complete 4-partite graph, with vertex sets $A,B,C,D$ each with 15 vertices. Color all edges in $(A,B),(B,C),(C,A)$ blue, and all else red. It is easy to check that there are no monochromatic cycles of length 3 or 5, and this graph has $\tbinom{4}{2}\cdot 15^2=1350$ edges, as needed. (This equality case is called the Turan Graph, without the coloring.)

Lemma 1: There cannot be any $K_5$ in the graph Proof. Denote the vertices of the $K_5$ as $v_1, v_2, \dots, v_5.$ I claim that there must be $3$ blue edges on the border of the $K_5$ and $2$ red edges on the border. Suppose there are only 4 blue edges $v_1v_2, v_2v_3, v_3v_4, v_5v_1$ (note that all of the blue edges are connected). And let the red edge be $v_4v_5.$ We get that $v_2v_4$ must be red, which implies $v_2v_5$ must be blue, a contradiction because $v_1v_2v_5$ becomes a monochromatic triangle:

If three of the border edges are blue and two are red, there are two cases:

$v_1v_2$ is red, $v_2v_3$ is blue, $v_3v_4$ is red, $v_4v_5$ is blue, $v_5v_1$ is blue. We get $v_1v_4$ must be red, which implies $v_1v_3$ to be blue, which causes $v_2v_4$ to be blue, which is a contradiction because $v_1v_5v_4v_2v_3v_1$ is a monochromatic 5-cycle.

: $v_1v_2$ is blue, $v_2v_3$ is red, $v_3v_4$ is red, $v_4v_5$ is blue, $v_5v_1$ is blue. We get $v_2v_4$ must be blue, which implies $v_2v_5$ and $v_1v_4$ must be red, which implies $v_3v_1$ and $v_3v_5$ must be blue, which makes $v_1v_3v_5$ a monochromatic triangle. Since we exhausted all cases, the lemma is proved. Now, by Turan's theorem, the largest number of edges we can have without a $K_5$ is $\left(1-\frac{1}{4}\right)\frac{60^2}{2} = 1350.$ A construction that works: Take a 4-partite graph with 4 sets of vertices, denoted as $A,B,C,D.$ Let all the edges between $(A,B), (B,C), (C,D), (D,A)$ be red and all other ones blue. It's easy to see this has no monochromatic triangles or 5-cycles. The graph has ${4 \choose 2}\cdot 15^2 = 1350$ vertices, as desired $\boxtimes.$

Nice problem! The following solution uses Turan's theorem. $Claim1)$ There are no $K_5$, that satysfy the property that there is no monochromatic cycles of length 3 and no monochromatic cycles of length 5. The proof of this is very easy but is mandatory to be written,my proof is very similar to the @above post. Now from the Turans Theorem we get an upper bound, that they are at most \[ E \le \left(1-\frac14 \right) \cdot \frac{60^2}{2} = 1350. \]edges. $Construction$.Even this is not all original,from the equality case of Turans theorem we get the following construction. Let us take a 4-partite graph with 4 sets of vertices $A,B,C,D$, such that 15 different vertices lie on each set. Now let us color the edges between $(A,B),(B,C),(C,A)$ in Red, and the rest in Blue, now its obvious that there are no monochromatic cycles of length 3 and 5.So we are done and the answer is $E=1350$ $\blacksquare$

The lemma:If we were to color all $10$ edges of $K_5$ with red and blue, we can find either a triangle or a $5$-cycle (not entirely obvious) where can we use it(may give some egs)

Here's a short proof of the main claim by Ankan Bhattacharya. Claim: If we were to color all $10$ edges of $K_5$ with red and blue, we can find either a monochromatic triangle or a $5$-cycle. Proof : Note that $5 >2^2$, so atleast one of the graphs formed by the red and the blue edges respectively must be non-bipartite and the conclusion follows.$\square$

The proof above seems false: note that $K_{3,2}$ is bipartite and has $6>5$ edges.

Not a great problem in my opinion. The answer is $\boxed{1350}.$ $\emph{Construction:}$ Divide the vertices into four sets $A,B,C,D$ of size $15.$ For any vertices $u,v,$ If $u\in A$ and $v\in B$ or vice-versa, connect $u$ and $v$ with a red edge. If $u\in A$ and $v\in C$ or vice versa, connect $u$ and $v$ with a blue edge. If $u\in A$ and $v\in D$ or vice versa, connect $u$ and $v$ with a blue edge. If $u\in B$ and $v\in C$ or vice versa, connect $u$ and $v$ with a blue edge. If $u\in B$ and $v\in D$ or vice versa, connect $u$ and $v$ with a blue edge. If $u\in C$ and $v\in D$ or vice versa, connect $u$ and $v$ with a red edge. This creates a total of $6\cdot 15^2=1350$ edges, and it is easy to check that no $3$-cycles or $5$-cycles are formed. $\emph{Proof: }$ Suppose the graph contains a $K_5.$ Then, by Mantel's Theorem, both the red subgraph of this $K_5$ and the blue subgraph of this $K_5$ contain at most $\lfloor\frac{25}{4}\rfloor=6$ edges. This yields two cases. $\textbf{Case 1: }$ Both the red subgraph and the blue subgraph have $5$ edges. Since there are no triangles, this implies that there is a red $5$-cycle and a blue $5$-cycle, contradiction. $\textbf{Case 2: }$ The red subgraph has $6$ edges and the blue subgraph has $4$ edges. Then, the red subgraph achieves the equality case of Mantel, so it must be $K_{2,3}.$ However, this forces the blue subgraph to have a triangle, contradiction. Now, by Turan's Theorem, the graph has at most $\frac{3}{8}\cdot 60^2=1350$ edges, as desired. GeronimoStilton wrote: The proof above seems false: note that $K_{3,2}$ is bipartite and has $6>5$ edges. A red $K_{3,2}$ can't exist because then a blue triangle would exist (hence the $2^2$ in @Aryan23's solution).

It's well-known that the only coloring of $K_5$ (up to automorphisms) with no monochromatic tringels is the following: Which contains a 5-cycle. Therefore, the graph contains no $K_5$, and Turan's theorem gives an upper bound of $$\left(1-\frac{1}{4}\right)\frac{60^2}{2}=1350$$To see that this can be accomplished, take the Turan graph $T(60,4)$, which splits the vertices into 4 sets $A,B,C,D$ of size 15, such that an edge is drawn between two vertices iff they belong to different sets. Color all edges between sets $A,C$ or $B,D$ red, and the remaining ones blue. It's easy to verify that it has no monochromatic tringels or 5-cycles, and it is indeed the equality case of Turan's theorem.

Solved with a small hint, but it seems that my proof of the main idea is quite a bit cleaner The answer is $1350$, which can be constructed by splitting the vertices of the graph into $S_1,\ldots,S_4$, each of $15$ vertices. Connect $S_1$ and $S_3$ with $S_2$ and $S_4$ using red edges, and connect $S_1$ with $S_3$, as well as $S_2$ with $S_4$ using blue edges. Then the graph with red edges only is bipartite, as is the graph with blue edges only, so they contain no odd cycles—thus this construction works. For the bound, the key idea is the following lemma: Lemma: $K_5$ is not colorable in this way. Proof: Any coloring of $K_5$ must be bipartite considering only both red and blue edges. If we partition the $K_5$ into "bipartite components" $A$ and $B$ according to the red edges, then one of $A$ and $B$ must have at least $\lceil 5/2 \rceil=3$ vertices, and thus contains a blue $K_3$ which isn't bipartite. $\blacksquare$ Now, by Turan's theorem, we have at most $(1-\tfrac{1}{4})\tfrac{60^2}{2}=1350$ edges, as desired. $\blacksquare$

Here is a solution to a more general version of the problem. Let $n$ be a positive integer. Find the maximum number $E$ such that the following holds: there is an edge-colored graph with $4n$ vertices and $E$ edges, with each edge colored either red or blue, such that in that coloring, there is no monochromatic cycles of odd length. Claim: $G$ contains no $K_5$ We will show that $K_5$ has a monochromatic cycle of odd length. Call the vertices $a$, $b$, $c$, $d$ ,$e$. Assume that there is a monochromatic cycle of length $4$, wlog $\{a,b\}$, $\{b,c\}$, $\{c,d\}$, $\{d,a\}$ are all red. To avoid any triangles, $\{a,c\}$ and $\{b,d\}$ are blue. If $\{e,a\}$ is red then $\{e,b\}$ and $\{e,d\}$ are blue. But then $\{b,d\}$, $\{d,e\}$, $\{e,b\}$ are all blue. So, none on the edges with endpoints $e$ are red, and thus must be blue. This clearly obviously produces an odd cycle. Now, assume there is no monochromatic cycle on length $4$. This implies that there are no monochromatic cycles. There are at least $5$ edges of at least one color, which implies that there is a cycle of that color. $\square$ So, by Turan's theorem. $G$ can not have more than $\frac{3 \cdot (4n)^2}{8} = 6n^2$ edges since it is $K_5$-free. For constructing $6n^2$ edges, we can partition $G$ into two subgraphs $A$ and $B$. Connect $A$ and $B$ with $K_{n,n}$ and connect $A$ to be with $K_{2n,2n}$. $\blacksquare$

Claim. $K_5$ cannot be colored as such. Proof. Consider the coloring of one $5$-cycle in the graph. If four of the edges of the cycle are colored blue, it follows by the $3$-cycle condition that the fifth one must be blue too, contradiction. On the other hand, if three consecutive edges are blue, then upon coloring through all the edges, we are forced to have a red $3$-cycle. If three non-consecutive edges are colored blue, then we will have a blue $5$-cycle using two of the non-cycle edges. Thus we have exhausted all cases and the coloring is impossible. $\blacksquare$ Then by Turan's theorem $E \leq \frac 34 \cdot \frac{60^2}2 = 1350$. For construction, partition $E$ into two subgraphs $A$ and $B$, both with $30$ vertices, such that all edges between $A$ and $B$ are connected, and $A$ and $B$ are themselves complete bipartite graphs on two partitions of size $15$.

Sorry for bad writeup. Let $G$ be a our graph. Claim: Color all edges of $K_{5}$ either blue or red. Then we can find monochromatic triangle or 5-cycle. Proof: Assume there exist $v \in K_{5}$ such that there exist $v_{1}, v_{2}, v_{3} \in K_{5}$ such that edge $vv_{i}$ is colored red. Then edge $v_{i}v_{j}$ is blue, so triangle $v_{1}, v_{2}, v_{3}$ is monochromatic. So every $v \in K_{5}$ there are exactly 2 red edges that incident in $v$. That means $K_{5}$ has monochromatic 5-cycle. $\blacksquare$ This implies our graph has no $K_{5}$. Then by Turan's theorem, we have $E \leq (1-\frac{1}{5-1})\frac{60^2}{2} = 1350$. Now construct graph with $E = 1350$ such that there are no monochromatic triangle and monochromatic 5-cycle. It remains to find a working construction. Let us partition the $60$ vertices into four groups $A_{1}, A_{2}, A_{3}, A_{4}$. Suppose we draw red edges between $(A_{1}, A_{2}), (A_{2}, A_{3}), (A_{3}, A_{4}), (A_{4}, A_{1})$ and blue ones between $(A_{1}, A_{3}), (A_{2}, A_{4})$. This does indeed give a total of $15^2 \cdot 6 = 1350$ edges, and a quick check shows that this does indeed have no triangles or $5$-cycles.$\blacksquare$

Solved with akliu. The answer is $\boxed{1350}$. This is achievable by partitioning the 60 vertices into $4$ subsets of $15$ vertices each and placing an edge between any two vertices in a different subset. Now we prove the bound. Claim: In a $K_5$ that has its edges colored blue or red, there is always a monochromatic cycle of length $3$ or one with length $5$. Proof: Assume there is no $K_3$ or $K_5$. Let the vertices of the $K_5$ be $v_1, v_2, v_3, v_4, v_5$. Notice there exists some $i$ with $v_i v_{i + 1}$, $v_{i + 1} v_{i + 2}$ are the same color, where indices are taken modulo $5$ (otherwise $v_1 v_2$ and $v_6 v_7 = v_1 v_2$ would have different color). Now, since all such $v_k v_{k + 1} $ can't be of the same color, there exists such $i$ where $v_i v_{i + 1} , v_{i + 1} v_{i + 2} $ are both the same color, but $v_{i+ 2} v_{i + 3}$ is the other color. WLOG $i = 1$ and the common color is red. So, the edges $v_1 v_2$ and $v_2 v _3 $ are blue, but $v_3 v_4 $ is red. If the edges $v_a v_b $ and $v_b v_c$ are of the same color, then $v_b v_c$ is of the other color. This implies that $v_1 v_3$ is red (same as $v_3 v_4$), so $v_1 v_4$ is blue (same as $v_1 v_2$), which means $v_2 v_4$ is red. Now we look at the color of $v_3 v_5$. Case 1: $v_3 v_5$ is red. Then it is the same color as $v_3 v_4$, so $v_4 v_5$ is blue (same as $v_1 v_4$), which means $v_1 v_5$ is red (same as $v_1 v_3$), so $v_3 v_5$ is blue, contradiction. Case 2: $v_3 v_5$ is blue. Then it is the same color as $v_2 v_3$, so $v_2 v_5$ is red (same as $v_2 v_4$), so $v_4 v_5 $ is blue (same as $v_1 v_4$), so $v_1 v_5$ is red (same as $v_1 v_3$. Now, $v_4 v_3$, $v_3 v_1$, $v_1 v_5$, $v_5 v_2$, and $v_2 v_4$ form a $5$-cycle that is all red, contradiction. Therefore, a $K_5$ cannot exist in the graph, so by Turan's Theorem, there are at most $\frac{ 3 \cdot (60)^2 }{8} = 1350$ edges, as desired.

The answer is $${4\choose 2}(15^2)=1350.$$ Claim: The graph has no $K_5$. Call 5 vertices $A,B,C,D,E$. WLOG $A$ has a red edge going to $B$ and $E$ (since it must have two outgoing edges of some color). Now, $EB$ must be blue. Since at least one of $DE$ and $DB$ is red, WLOG $DE$ is red, since the current configuration is symmetric. This then forces $EB$ to be blue. If $CD$ was red, then $EC$ is forced blue, but this would force $BC$ to be red, but then that creates a red 5-cycle, contradiction. However, if $CD$ is blue, then $AC$ is forced to be red, making $BC$ blue. However, now $CE$ can be neither red nor blue, a contradiction. Thus, by Turan's Theorem, the maximum number of edges in a $K_5$-free graph with 60 vertices is from a $K_{15,15,15,15}$, which as $1350$ edges, establishing the bound. For the construction, split the vertices into 4 groups of 15, call them $A,B,C,D$. Make all edges from $A$ to $B$, $B$ to $C$, and $C$ to $D$ red, but make $C$ to $A$, $A$ to $D$, and $D$ to $B$ blue. In this construction, since each color is a 4 vertex path, there is no way to follow an odd number of edges in that path to end back at the starting group, so there is no monochromatic 3-cycle or 5-cycle. remark: This solution is in my opinion quite natural. Of course, the first thing one tries to do is replace $60$ with smaller numbers. We first encounter issues at $n=5$, and we see that we are unable to complete the graph. This by itself allows us to get a bound for general case using Turan's. However, note that the equality case of Turan's is a complete $n-1$-partite graph, so this strongly motivates looking at such a case for our construction. The most naive thing to do is to make all edges between two groups the same color, and this happens to work. Additional comment: This solution also works in the more general problem of preventing all odd cycles.

trivel 20 mohs 5 sec solve?? It is easy to see that $K_5$ is a forbidden subgraph. By Turán $E\leq\boxed{1350}$. Construction is $K_{15}^4$ with edges between parts $1$ and $2$ and edges between parts $3$ and $4$ colored red. Note that the red graph and blue graph are both bipartite so there are no odd cycles. $\square$

Amazing question