In a school with students each student has exactly friends and among any three students there are two which are not friends. Find the largest possible value of .
Solution
Answer: 808.
Let us reformulate the problem in terms of graph theory: a -regular graph on vertices does not contain any triangle. What is the largest value of ? Below we give an example for :

Now we show that . First of all, suppose that is bipartite: where all edges are between and . Then since we get which is impossible since there are vertices. Hence is not bipartite and contains a cycle of odd length. Let be the shortest odd cycle with edges. Since does not contain any triangle .
Let us show that any vertex in has at most two neighbours on . On the contrary, suppose that vertices (in clockwise direction) are directly connected to . Let be the number of vertices on paths (without endpoints) , , of , respectively. Since has no triangles . Since , one of these three numbers, say , is even. The vertex and constitute a cycle of length . Since is odd and is a shortest odd cycle, we get and . Hence we get a contradiction .
Let us consider all edges between and . Since each vertex of has neighbours there are edges between and . On the other hand, each vertex of has at most two neighbours in . Therefore,
Finally, since we get . Done.