Given $30$ students such that each student has at most $5$ friends and for every $5$ students there is a pair of students that are not friends, determine the maximum $k$ such that for all such possible configurations, there exists $k$ students who are all not friends.
Problem
Source: China Mathematical Olympiad 2015 Q5
Tags: combinatorics proposed, combinatorics
21.12.2014 15:39
The answer is $k=6$.. Now,proof that we can always make $6$ students such that no two are friends.Start with one student.If the size of the current group is $s<5$ we can just add one more student because then we will have $5s>=30-s$ and that is a contradiction.If the size of the current group is $s=5$,then if there exist a guy among $25$ others that doesn't know anybody,we just add him,if not then all the guys from the group $s$ will know $5$ people and there won't exist a guy among $25$ others that knows two or more guys from $s$,so just pick a guy from $g$ $s$ and a group of guys that he knows,now among those guys we will have $2$ that don't know each other,so just add those two guys and remove $g$,so we built a group of $6$ people
22.12.2014 01:53
No.The answer is k=6.
22.12.2014 15:01
Ok,I was dumb,I didn't see an example for $k=2$ when there are $10$ students and that is the flaw in my proof.An example for $k=6$ goes like this:Divide $30$ students in $3$ groups of $10$ students and students that are not in the same group are never frieds.Now,labell students in one group $1,2,...10$.The connections go like this: ($1-5,1-6,1-7,1-3,1-4,2-3,2-4,2-8,2-9,2-10,5-6,5-7,6-7,$ $8-9,8-10,9-10,3-4,5-8,5-10,6-8,6-10,3-6,3-9,4-6,4-9$). And the proof that we can always find $6$ of them is the same as im my previous post.
22.12.2014 15:45
The proof cannot be the same, since you've "proved" one can always find $7$, and that was wrong, so the "proof"was wrong and has to be redone. By the Caro-Wey theorem $\alpha(G) \geq \sum_{v\in V} \dfrac {1} {1+\deg v} \geq \sum_{v\in V} \dfrac {1} {6} = 5$. Assume $\alpha(G) = 5$; this is equivalent to $\omega(\overline{G}) = 5$. But the number of edges of $\overline{G}$ is precisely the Turán number for a graph not containing a $K_6$, for which the only model is the complete $5$-partite graph $\overline{G} = K_{6,6,6,6,6}$. This means $G$ is the union of five disjoint $K_6$'s, absurd, since $G$ does not contain even a $K_5$. Therefore it must be $\alpha(G) > 5$, thus $\alpha(G) \geq 6$. Therefore, assuming your model is correct, the condition in the statement of the problem can be relaxed to "for every 6 students there is a pair of students that are not friends". An easy to grasp model for a $5$-regular graph $H$ on $10$ vertices, having $\alpha(H)=2$ and no $K_5$ subgraph, is to use $\mathbb{Z}_{10}$ as the vertex-set, and edges $\{i,i+1\}, \{i,i+4\}, \{i,i+5\}, \{i,i+6\}, \{i,i+9\}$ for all $i\in \mathbb{Z}_{10}$. Then the model for $G$ is the union of three disjoint copies of $H$.
22.12.2014 18:59
I mentioned that the flaw in my proof is the part when I was building a group of $7$ people and I built a group of $6$ people in my previous proof in exact same way as you did and the exapmle is also exactly the same as mine.
26.12.2014 04:22
Why do you have to use the Caro-Wey theorem? Can't you use what you said? That is, you want a graph such that its complement does not have a $K_5$, and such that it has at most $\dfrac{30\cdot5}{2}$ edges. Notice that the graph which has the least edges satisfying that condition is the complement of the Turán's graph, and it has exactly as many edges as required, and any other graph has more edges. and (by Turán) thus does not fit the requirement for the number of edges. Thus the answer is at least $6$ and then you give your example, which is awesome.
11.03.2015 02:58
In the language of graph theory, the problem can be rephrased as follows: Given any regular graph with $30$ vertices and degree $5$ such that there are no $K_5$'s, find the maximum $k$ such that there always exists an independent set of size $k.$ Now, we claim that the answer is $k = 6.$ To show that $6$ is the maximum, we need only provide an example of a graph satisfying the above conditions such that the maximum size of any independent set in this graph is $6.$ So, consider a graph $G$ with ten vertices: $v_1, v_2, v_3, v_4, v_5, w_1, w_2, w_3, w_4, w_5.$ Construct two cycles $v_1v_2v_3v_4v_5$ and $w_1w_2w_3w_4w_5$, and for $i, j\in \{1, 2, 3, 4, 5\}$, join $v_i$ and $w_j$ if and only if $i - j \equiv 0, \pm 1 \pmod 5.$ We will show that the maximal size of an independent set of $G$ is $2.$ Suppose, for the sake of contradiction, that $G$ contains an independent set of size at least $3.$ Then by the Pigeonhole Principle, at least two vertices must lie in one cycle; WLOG, let these two vertices be $v_1, v_3.$ Since the $v$-cycle can accommodate no more vertices, a third vertex must lie in the $w$-cycle. However, it is easy to see that any vertex in the $w$-cycle is connected to either $v_1$ or $v_3.$ This is a contradiction, so we conclude that $G$ has no independent set of size $3.$ Furthermore, we claim that $G$ contains no $K_5.$ Once again, suppose for the sake of contradiction, that $G$ does contain a $K_5.$ Then by the Pigeonhole Principle, at least three of these five vertices must lie on one cycle; WLOG, let these three vertices be $v_1, v_2, v_3.$ But then we require two vertices in the $u$-cycle that are each connected to $v_1, v_2, v_3.$ However, there is only one such vertex, $u_2$, so we conclude that this is impossible. Hence, it is clear that $G$ is a $K_5$-free regular graph with degree $5$ such that the maximum size of an independent set of $G$ is $2.$ Now, consider a graph $G'$ that consists of three copies of $G.$ Then the maximum size of an independent set of $G'$ is no more than three times the maximum size of an independent set of $G.$ Therefore, $G'$ is a $K_5$-free regular graph with degree $5$ such that the maximum size of an independent set of $G'$ is no more than $6.$ We have just found our desired graph, so we conclude that $k = 6$ is indeed an upper bound. $\blacksquare$ Lastly, we need to show that any graph that satisfies the conditions of the problem statement contains an independent set of size $6.$ But this is just a straightforward application of Turan's Theorem. We proceed by the principle of contradiction: Take any graph $G$ satisfying the necessary conditions, and consider its complement, $\overline{G}.$ We easily find that $\overline{G}$ has $30$ vertices and at least $\binom{30}{2} - \frac{30 \cdot 5}{2} = 360$ edges. Now, suppose by way of contradiction that $\overline{G}$ does not have a $K_6.$ Then by Turan's Theorem, $G$ can have at most $\left(1 - \frac{1}{5}\right)\frac{30^2}{2} = 360$ edges. Therefore, either we have reached our necessary contradiction, or $\overline{G}$ has precisely $360$ edges and equality holds in Turan's Theorem. However, equality holds in Turan's Theorem if and only if $\overline{G}$ is a Turan Graph. But it is clear that this Turan Graph would then have an independent set of size $6$ (in particular, $\overline{G}$ would have at least five independent sets of size $6$), so $G$ would have a $K_6.$ This is a contradiction since $G$ cannot even have a $K_5.$ Hence, we have proven that any graph satisfying the conditions in the problem statement has an independent set of size $6$, and so we're done. $\square$
03.09.2015 15:41
This was on the China National Olympiad.