I asked a question few days ago which was from a local math contest in my city. The question and the solution seems interesting to me and I am interested in solving the generalization of the problem. So, the generalized problem is as follows:
Professor Liyung wants to make a math club consisting of his $n$ students. But there is a problem. Each student is enemies with exactly $k$ ($1\leq k \leq n-1$) 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 all possible values of $M$. (If student $A$ is an enemy with student $B$, then student $B$ is an enemy with student $A$. Student $A$ is not enemy with himself.)
Here, $n,k$ are given numbers such that they satisfy the conditions of the problem (i.e. it is possible to draw a graph with $n$ vertices each of the vertices having degree $k$). Here are my workings regarding the problem:
My workings
I first tried for a fixed value of $k$. And I got the following:
- For $k=1$, the problem statement is true for only even $n$. Then, $M$ has only one possible value that is $\frac n 2$.
- For $k=2$, all values of $M$ are possible in the range $[\lceil\frac n 3\rceil,\lfloor\frac n 2\rfloor]$. (Explanation is in the link.)
- For $k=3$, the upper bound of $M$ is $\lfloor \frac n 3\rfloor$ and the lower bound of $M$ is $\lceil\frac n 4\rceil$. However, I don't have a nice argument to prove the upper bound. The proof of the lower bound is as follows:
Proof: If we choose $\lceil\frac n 4\rceil -1$ students as members, then there are at most $3\lceil\frac n 4\rceil -3$ students who can't be members of the club. Then, we can choose at least $1$ students from the remaining students as a member of the club. This proves that $M$ is at least $\lceil\frac n 4\rceil$ for $k=3$.
So, I think all values of $M$ are in $[\lceil\frac{n}{k+1}\rceil,\lfloor\frac{n}{k}\rfloor]$. The lower bound can be proved by following the similar steps as in for $k=3$. However, I am unable to show that all values in $[\lceil\frac{n}{k+1}\rceil,\lfloor\frac{n}{k}\rfloor]$ can be a value of $M$.
I hope my thoughts are correct. I need to complete the solution i.e. proving the upper bound and showing that all values in the stated interval are possible. The original problem involves graph theory in its solution. So, can the generalized problem be solved with graph theory?
Best Answer
You are right about the lower bound, but not the upper. The correct upper bound is $\lfloor n/2\rfloor$ for any fixed value of $k\leq n/2$.
To see that this is an upper bound, fix a club with $M$ members and count edges of the graph, i.e. pairs who are enemies. There must be $Mk$ pairs with exactly one person in the club (each person in the club has $k$ enemies, none of whom are in the club). There are some number $r\geq 0$ of pairs who are both outside the club. Now everyone not in the club has $k$ enemies, and that gives $(n-M)k$ ordered pairs where the first person is not in the club. This counts each of the $Mk$ pairs with exactly one person in the club once, and each of the $r$ pairs of two non-members twice. So $(n-M)k=2r+Mk$, and since $r\geq 0$ we have $n-M\geq M$.
This bound can be achieved for any even $n$. (If $k$ is odd, then any graph with every vertex having degree $k$ must have $n$ being even.) To see this, start with the complete bipartite graph with both parts having size $n/2$ - every vertex has degree $n/2$. Now remove a perfect matching, which exists by Hall's theorem (a corollary of Hall's theorem is that any regular bipartite graph - unless it is $0$-regular - has a perfect matching). This decreases all degrees by $1$. Keep doing this until every degree is $k$. Clearly either part of the original graph contains no edges, so is a valid club, and has size $n/2$.
Now to obtain anything in between the two bounds, you just need to mix the two constructions. E.g. if $k=3$ and $n=100$ you can get $M=25$ by taking $25$ copies of $K_4$, or $M=50$ by the construction above. To get, say, $M=41$, take $9$ copies of $K_4$ and do the construction above on the remaining $64$ vertices. Your optimal club will then have one person from each $K_4$ and $32$ people from the remainder.