Question 99
Let $n,k$ be positive integers with $n\ge k+1$. There are $n$ countries on a planet. Some pairs have diplomatic relations, and every country has relations with at least $k$ other countries. An evil villain, Duransha, carries out the following plan.
- First he chooses distinct countries $A,B$ to lead two camps $\mathcal A,\mathcal B$, respectively, with $A\in\mathcal A$ and $B\in\mathcal B$.
- Each remaining country chooses one of these two camps.
- After all choices have been made, every diplomatic relation between a country in $\mathcal A$ and a country in $\mathcal B$ is severed.
Prove that, whatever the initial diplomatic relations, he can choose $A,B$ so that at least $k$ relations are severed, regardless of the countries' choices.
- First he chooses distinct countries $A,B$ to lead two camps $\mathcal A,\mathcal B$, respectively, with $A\in\mathcal A$ and $B\in\mathcal B$.
- Each remaining country chooses one of these two camps.
- After all choices have been made, every diplomatic relation between a country in $\mathcal A$ and a country in $\mathcal B$ is severed.
Prove that, whatever the initial diplomatic relations, he can choose $A,B$ so that at least $k$ relations are severed, regardless of the countries' choices.