Maths Olympiad Prep

Library / /19 of 48

Combinatorics Difficulty 6.3 National Olympiad Prove it Turkey

In a school with 20212021 students each student has exactly kk friends and among any three students there are two which are not friends. Find the largest possible value of kk.

Solution

Answer: 808.

Let us reformulate the problem in terms of graph theory: a kk-regular graph GG on 20212021 vertices does not contain any triangle. What is the largest value of kk? Below we give an example for k=808k = 808:

Figure 1

Now we show that k808k \le 808. First of all, suppose that GG is bipartite: G=(A,B)G = (A, B) where all edges are between AA and BB. Then since Ak=Bk|A| \cdot k = |B| \cdot k we get A=B|A| = |B| which is impossible since there are 20212021 vertices. Hence GG is not bipartite and GG contains a cycle of odd length. Let CC be the shortest odd cycle with 2t+12t+1 edges. Since GG does not contain any triangle t2t \ge 2.

Let us show that any vertex vv in GCG-C has at most two neighbours on CC. On the contrary, suppose that vertices a,b,cCa, b, c \in C (in clockwise direction) are directly connected to vv. Let nab,nbc,ncan_{ab}, n_{bc}, n_{ca} be the number of vertices on paths (without endpoints) (a,b)(a, b), (b,c)(b, c), (c,a)(c, a) of CC, respectively. Since GG has no triangles nab,nbc,nca1n_{ab}, n_{bc}, n_{ca} \ge 1. Since nab+nbc+nca=2t2n_{ab} + n_{bc} + n_{ca} = 2t-2, one of these three numbers, say nabn_{ab}, is even. The vertex vv and (a,b)(a, b) constitute a cycle of length nab+3n_{ab}+3. Since nab+3n_{ab}+3 is odd and CC is a shortest odd cycle, we get nab+32t+1n_{ab}+3 \ge 2t+1 and nab2t2n_{ab} \ge 2t-2. Hence we get a contradiction nbc+nca=0n_{bc} + n_{ca} = 0.

Let us consider all edges between CC and GCG-C. Since each vertex of CC has kk neighbours there are (k2)(2t+1)(k-2)(2t+1) edges between CC and GCG-C. On the other hand, each vertex of GCG-C has at most two neighbours in CC. Therefore,
2(20212t1)(k2)(2t+1)4042k(2t+1). 2(2021-2t-1) \geq (k-2)(2t+1) \Rightarrow 4042 \geq k(2t+1).
Finally, since t2t \geq 2 we get k808k \leq 808. Done.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.