Skip to main content
1 of 2

Minimizing the maximum degree of a set of sets

Suppose that ${\cal C}$ is a set of subsets of $\{1,\ldots,n\}$ with the following properties:

  1. $\{1,\ldots,n\}\notin {\cal C}$, and
  2. for all $x,y\in \{1,\ldots, n\}$ there is $A\in {\cal C}$ such that $\{x,y\}\subseteq A$.

For $j\in \{1,\ldots,m\}$ we set the degree of $j$ to be $\text{deg}(j) = |\{A\in {\cal C}: j\in A\}|$ and set $$m({\cal C}) = \max\big\{\text{deg}(j): j\in\{1,\ldots,n\}\big\}.$$

Is it possible that $m({\cal C}) < n-1$? If yes, how small in terms of $n$ can $m({\cal C})$ become?

(You only need to answer the first question to get the answer accepted; the second question is a bonus question.)