MathDB

A team contest between

n

participants is to be held. Each of these participants has exactly

k

enemies among the other participants. (If

A

is an enemy of

B

, then

B

is an enemy of

A

. Nobody is his own enemy.) Assume that there are no three participants such that every two of them are enemies of each other. A subversive enmity will mean an (un-ordered) pair of two participants which are enemies of each other and which belong to one and the same team. Show that one can divide the participants into two teams such that the number of subversive enmities is

\leq\frac{k\left(n-2k\right)}{2}

. (The teams need not be of equal size.) Note. The actual source of this problem is: Glenn Hopkins, William Staton, Maximal Bipartite Subgraphs, Ars Combinatoria 13 (1982), pp. 223-226. It should be noticed that

\frac{k\left(n-2k\right)}{2}\leq\frac{n^{2}}{16}

, so the bound in the problem can be replaced by

\frac{n^{2}}{16}

(which makes it weaker, but independent of

k

). darij

Problem Statement