MathDB

Let

k\ge 1

be an integer and

\mathsf S

be a family of 2-element subsets of the index set

\{1,\ldots,2k\}

with the following property: if

\mathsf M_1,\ldots,\mathsf M_{2k}

are arbitrary sets such that \mathsf M_i\cap\mathsf M_j\neq\emptyset \Leftrightarrow \{i,j\}\in\mathsf S, then the union

\mathsf M_1\cup\ldots\cup\mathsf M_{2k}

contains at least

k^2

elements. Show that there is a suitable family

\mathsf S

for any integer

k\ge1.

Problem Statement