Number of subsets when each pair of distinct elements is contained in exactly one subset Let $E$ be a set of cardinality $n$. Suppose $M_1, M_2, .. , M_m$ are
   distinct proper subsets of $E$ such that for each pair of distinct elements $x_1, x_2\in E$, there is exactly one $M_i\supseteq\{x_1,x_2\}$. Prove that $m \ge n$.


It's obvious $n$ has to be greater or equal to $3$. Also, for $n=3$, it's easy to prove it, but I have no idea how to extend it. I think a proof using induction by $n$ is possible.
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 &amp;= \det \left((a_{11}-1) e_1 + J, \ldots, (a_{nn}-1)e_n + J\right)\\
&amp;=\det \left((a_{11}-1)e_1, \ldots, (a_{nn}-1)e_n \right) \\ &amp;+ \sum_{j=1}^n \det \left((a_{11}-1)e_1, \ldots, J (j-\textrm{th column}), \ldots,  (a_{nn}-1)e_n \right)\\
&amp;=\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 &amp; 0 &amp; 1 &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 \\ 0 &amp; 1 &amp; 0 &amp; 1 &amp; 1 \\    1 &amp; 0 &amp; 0 &amp; 0 &amp; 1
\end{pmatrix},  \ \ \ 
MM^T=\begin{pmatrix} 3 &amp; 1 &amp; 1 &amp; 1 \\ 1 &amp; 2 &amp; 1 &amp; 1 \\ 1 &amp; 1 &amp; 3 &amp; 1 \\ 1 &amp; 1 &amp; 1 &amp; 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\}$.
Take $E = \{ x_1, x_2\}$. 
There exist a set $M_{1,2}$ such that $x_1, x_2 \in M_{1,2}$. 

But then $M_{1,2} = E$. This is a direct contradiction to the theorem.

Thus this doesn't work for $n&lt;3$.