Exercise 18. During an Animath internship, each of the 2021 students has $k$ friends (if A is a friend of B, B is also a friend of $A$). However, there is no group of 3 students who are all pairwise friends. What is the maximum value of $\mathrm{k}$?
Solution to Exercise 18 Let G be the graph of friendship relations (undirected). We start by noting that G is not bipartite. Indeed, otherwise the sum of the degrees of the vertices in the first part would be equal to that of the second part. However, all vertices have degree k and there is an odd number of them, so there cannot be the same number on each side. This is therefore absurd.

We can thus consider a cycle C of minimal odd length r. We note that, if we take a vertex \( v \in G \backslash C \), it has at most two neighbors in C. Indeed, if it has at least 3, let's denote them \( v_{1}, v_{2}, v_{3} \) and let \( d_{i} \) be the distance from \( v_{i} \) to \( v_{i+1} \) following C in the chosen direction (with \( v_{4}=v_{1} \)). Then if we look at the cycles obtained by going from \( v_{i} \), to \( v_{i+1} \) (following C, in the chosen direction), then to \( v \) and back to \( v_{i} \), they are of length \( d_{i}+2 \). Since \( d_{1}+d_{2}+d_{3}=r \) is odd, one of these cycles is of odd length. Moreover, two of the \( v_{i} \) cannot be adjacent, otherwise we would have a triangle. Therefore, each of the \( d_{i} \) is at least 2, so the one that is odd is at most \( r-4 \), and we have thus created a cycle of odd length strictly smaller than r, which is absurd.

![](https://cdn.mathpix.com/cropped/2024_06_04_7f99ab0e41c82ac4a4c9g-21.jpg?height=653&width=653&top_left_y=980&top_left_x=736)

Furthermore, in C, each vertex can only be connected to its two neighbors in the sense of C. Indeed, if \( v, w \in C \) are not neighbors in C and are connected, then we can go from one to the other by passing through the cycle with an even number of edges, and thus by \( r' \leq r-3 \) edges. Then, by returning via the edge that connects \( v \) and \( w \), we have created an odd cycle of length strictly smaller than r, which is absurd.

![](https://cdn.mathpix.com/cropped/2024_06_04_7f99ab0e41c82ac4a4c9g-21.jpg?height=521&width=571&top_left_y=1905&top_left_x=777)

This gives the inequality, by counting the sum of the degrees of the edges of C: \( k r \leq 2(n-r)+2 r=2 n \). Therefore, \( k \leq \frac{2 n}{r} \). Since \( r \geq 5 \), this gives \( k \leq 808 \) with \( n=2021 \).

Now let's construct a graph achieving this value of k. We divide the students into 5 groups: one of size 403, two of size 404, and two of size 405. We connect the students in the group of size 403 to those in the groups of size 404, those in the first group of size 404 to those in the first group of size 405, and similarly for the second groups. Then, we take a bijection between the two groups of size 405 and connect the students in the two groups of size 405 except if they are associated by the bijection. We have the desired result.

![](https://cdn.mathpix.com/cropped/2024_06_04_7f99ab0e41c82ac4a4c9g-22.jpg?height=528&width=683&top_left_y=468&top_left_x=713)

## Graders' Comments:

No points were awarded for this exercise. The brave students who attempted this exercise did not find the correct maximum value.