MathDB

Let

n

and

k

be positive integers, with

n\geq k+1

. There are

n

countries on a planet, with some pairs of countries establishing diplomatic relations between them, such that each country has diplomatic relations with at least

k

other countries. An evil villain wants to divide the countries, so he executes the following plan:
(1) First, he selects two countries

A

and

B

, and let them lead two allies,

\mathcal{A}

and

\mathcal{B}

, respectively (so that

A\in \mathcal{A}

and

B\in\mathcal{B}

).
(2) Each other country individually decides wether it wants to join ally

\mathcal{A}

\mathcal{B}

.
(3) After all countries made their decisions, for any two countries with

X\in\mathcal{A}

and

Y\in\mathcal{B}

, eliminate any diplomatic relations between them.
Prove that, regardless of the initial diplomatic relations among the countries, the villain can always select two countries

A

and

B

so that, no matter how the countries choose their allies, there are at least

k

diplomatic relations eliminated.
Proposed by YaWNeeT.

Problem Statement