Maximum number of members in the math club

combinatoricscontest-mathextremal-combinatoricsextremal-graph-theorygraph theory

Problem: Professor Liyung wants to make a math club consisting of his $40$ students. But there is a problem. Every student is enemies with two other students. And no one wills to be a member of the club if any of his enemies is already a member of the club. Let $M$ be the maximum number of members the club can have. Find the sum of all possible values of $M$. (If student $A$ is an enemy with student $B$, then student $B$ is an enemy with student $A$.)

This is a problem from a local math contest in my city held on last month. Here is the solution I think of :

My thoughts: For every student chosen to be in the club, two students can't be a member of the club. So, the maximum number of members of the club is $20$.

I'm confused of the statement "Find the sum of all possible values of $M$" as there is only one value of $M$ in my solution. And I also believe that the problem would not be so easy as this was the second last problem in the contest and most of the problems there were not easy. But I couldn't think of other solution to the problem.
So, I want to know if my solution is correct or not. If not, what is the correct solution?

Update: A generalization to this problem has been discussed here.

Best Answer

Let $M$ be maximal subset of students no two in it are enemy. Then each student not in $M$ has at least one enemy in $M$ and every one in $M$ has exactly two enemies in $G\setminus M$. So by double counting we have $$2\cdot |M| \geq |G|-|M|\implies |M|\geq {|G|\over 3} \implies |M|\geq 14$$

Now for the upper bound. If we consider this group $G$ of students as a graph when two vertices are connected iff they are enemies, then we see this graph is, since each vertex has degree exactly $2$, disjoint union of some cycles $C_1,C_2,...C_k$. Since $\varepsilon = 40$ we have $$ |C_1|+|C_2|+...+|C_k| = 40 $$ But we can take at most half vertices from each cycle in $M$ so $|M|\leq 20$.

All values between $14$ and $20$ can be achieved:

  • For $|M|=14$ take every second vertex on $C_{4}$ and one vertex from each of twelve $C_3$.
  • For $|M|=15$ take every second vertex on $C_{10}$ and one vertex from each of ten $C_3$.
  • For $|M|=16$ take every second vertex on $C_{16}$ and one vertex from each of eight $C_3$.
  • For $|M|=17$ take every second vertex on $C_{22}$ and one vertex from each of six $C_3$.
  • For $|M|=18$ take every second vertex on $C_{28}$ and one vertex from each of four $C_3$.
  • For $|M|=19$ take every second vertex on $C_{34}$ and one vertex from each of two $C_3$.
  • For $|M|=20$ take every second vertex on $C_{40}$.

So, the result is $119$.

Related Question