Number of subsets when each pair of distinct elements is contained in exactly one subset

Solution for general case

Let $E=\{1,2,\ldots, n\}$. Define column vectors $v_j=(v_{ij})^T$ with $v_{ij}= \mathbf{1}_{M_j}(i)$ which gives $1$ if $i\in M_j$ and $0$ otherwise. Then $M=(v_{ij})$ is an $n\times m$ matrix consisting of $0$, $1$ entries. Our goal is to prove that $\mathrm{rank}(M)=n$. We will show this by proving that the rows of $M$ are linearly independent. Then the columns $v_j$ form an spanning set for $\mathbb{R}^n$ and it will follow that $m\geq n$.

According to the assumptions, for each $i$, there are at least two sets $M_{j_1}$ and $M_{j_2}$ such that $i\in M_{j_1}\cap M_{j_2}$. Otherwise, the pairs $\{i,1\}$, $\ldots$, $\{i,n\}$ are all included in one set $M_k$ which gives $M_k=E$. Thus, we see that any row of $M$ contains at least two $1$'s.

Consider a $n\times n$ matrix $MM^T$. If $MM^T$ is nonsingular then the rows of $M$ are linearly independent. For the proof, let $M^T x = 0$ for some $x\in\mathbb{R}^n$. Then $MM^T x = 0$. Since $MM^T$ is nonsingular, $x=0$. Write the rows of $M$ as $R_1, \ldots , R_n$. Then $MM^T = (b_{ij})$ with the dot product $b_{ij}=R_i\cdot R_j$.

Since any row has at least two $1$'s, we have $b_{ii}\geq 2$. Since any pair $\{i, j\}$ with $i \neq j$ is in exactly one $M_k$, we have $b_{ij}=1$ for $i\neq j$. Writing the determinant as a multlinear function on columns, we obtain that $$\det MM^T \geq 1+n.$$ Therefore we conclude that $MM^T$ is nonsingular, and we are done.

Proof of the determinant inequality

Let $A=(a_{ij})$ be a $n\times n$ matrix with $a_{ij} = 1$ for $i\neq j$, and $a_{ii}\geq 2$. Then $\det A \geq 1+n$. For the proof, let $J=(1, 1, \ldots, 1)^T$, and write the determinant as a multilinear function on columns:
$$ \begin{align} \det A &= \det \left((a_{11}-1) e_1 + J, \ldots, (a_{nn}-1)e_n + J\right)\\ &=\det \left((a_{11}-1)e_1, \ldots, (a_{nn}-1)e_n \right) \\ &+ \sum_{j=1}^n \det \left((a_{11}-1)e_1, \ldots, J (j-\textrm{th column}), \ldots, (a_{nn}-1)e_n \right)\\ &=\prod_{i=1}^n (a_{ii}-1) + \sum_{j=1}^n \frac{\prod_{i=1}^n (a_{ii}-1)}{a_{jj}-1}\geq 1 + n. \end{align}$$

An Example for $n=4$

An example of such matrix $M$ is $$ M=\begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix}, \ \ \ MM^T=\begin{pmatrix} 3 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}, \ \ \ \det MM^T = 16.$$

Possibility of $m=n$

Note that it is possible to have $n$ distinct subsets $M_1, \ldots, M_n$ satisfying the requirements. Let $M_1=\{2,3,\ldots, n \}$, $M_2=\{1,2\}$, $M_3=\{1,3\}$, $\ldots$, $M_n = \{1, n\}$.