Problem 8. The edges of a graph with $2 n$ vertices, $n \geq 4$, are colored in blue and red such that there is no a blue triangle and there is no a red complete subgraph with $n$ vertices. Find the least possible number of the blue edges.
8. We call a graph, satisfying the given condition, $n$-purple. Let $f(n)$ be the smallest possible number of blue edges in an $n$-purple graph.

Suppose that $f(n)f(n)$ for $n \geq 5$, we may find a vertex $a$ of $G$ that is the head of at most one blue edge. If $a$ is not head of a blue edge, then there is vertex $b$ of the graph $G \backslash\{a\}$ that is a head of a blue edge and hence $G \backslash\{a, b\}$ is a ( $n-1$ )-purple graph. If $a$ and $b$ are jointed by blue edge, then $G \backslash\{a, b\}$ is a ( $n-1$ )-purple graph. In both cases the obtained $(n-1)$-purple graph has at least one blue edge less than $G$ and so $f(n) \geq f(n-1)+1$. Then $f(n-1)<n+4$, in particular, $f(4)<9$.

Now we shall compute $f(4)$. It is well-known that there are 3 -purple graphs. Then the above arguments show that any vertex of a 4 -purple graph is a head of at least two blue edges. Hence $f(4) \geq 8$. If $f(4)=8$, then any vertex is a head of exactly two blue edges. There are two such graphs containing no blue triangles but these graphs are not purple. If $f(4)=9$, the two vertices are heads of three blue edges, and the remaining six vertices are heads of two blue edges. There are six such graphs containing no blue triangles but they are not purple. The following example shows that $f(4)=10$ - a regular octagon with blue sides and two blue adjacent main diagonals, and the remaining diagonals are red.

So $f(n) \geq n+5$ for $n \geq 5$. It is easy to see that the graph with $2 n$ vertices such that its blue edges form three disjoint cycles with lengths 5,5 and $2 n-10$ is $n$-purple. Hence $f(n)=n+5$ for $n \geq 5$.