How to generate a list of two-element sets that make all possible four-elements sets? I have a list of 6 elements (A...F) that I need to organize into the smallest number of unique two-element combinations (AB, AC, etc) possible so that they form all possible four-element combinations (AB + CD = ABCD). The order of the elements is unimportant and I can use each two-element combination as many times as possible (i.e. AB + CD, but also AB + EF)  
I know that: 
-There are fifteen possible 4-way combinations and 
-it should be solvable with 9 two-element combinations
...but I can't figure out conceptually how to generate my list of two-element combinations. 
Any ideas on how I could get started on this?
 A: Workable solution: $AB,\ AC,\ AD,\ EF,\ BC,\ BE,\ CF,\ DE$ and $ DF$.
This was mostly done by brute force but with some insights: 
Every letter has to appear at least 3 times in one of the nine pairs. Suppose it did not and we only had $AB$ and $AC$, then $ADEF$ could not be formed. Since there are only $18$ letters in $9$ pairs this means that every letter has to appear exactly $3$ times.
This gives us a start with $AB$, $AC$ and $AD$. It follows we need $EF$. To make $ABCD$ we need to add $BC$, $CD$ or $EF$. Due to symmetry the choice is arbitratry so we can pick $BC$. The rest of the pairs have to contain either $E$ or $F$ to ensure those appear often enough, giving us $BE$, $CF$, $DE$ and $DF$.
A: Let's formalize your problem a little:
Given a Universe $U= \{A_1,...,A_n\}$, we're searching for the smallest $C\subseteq \binom{U}{2}$ so that $\binom U 4\subseteq P(C)$.
(Here, $\binom{U}{k} := \{M\subseteq U\mid |M| = k\}$ i.e. $\binom{U}{k}$ consists of all sets of $k$-element subsets of $U$.)
This already gives us a way to brute-force the whole thing:


*

*Compute $P(\binom{U}{2})$, i.e. the set of all possible combinations of 2-element pairs

*For each element $M\in P(\binom{U}{2})$, test $\binom{U}{4}\subseteq \{K\mid \ \exists S_1,S_2\in M: S_1\cup S_2 = K \}$

*Choose the smallest $M$ that fulfills this test.


Note that this is the raw brute-force algorithm. There are many optimizations, both obvious and unobvious to improve this algorithm.
A: You can solve this problem via integer programming as follows.  Let binary variable $x_{ij}$ indicate whether pair $\{i,j\}$ (with $i < j$) is selected, and let binary variable $y_{i j k\ell}$ represent the product $x_{ij} x_{k\ell}$, where $\{i,j\} \cap \{k,\ell\} = \{\}$ and $i<k$.  Let $Q = \{(i,j,k,\ell):i<j<k<\ell\}$.  Then the problem is to minimize $\sum_{i,j} x_{ij}$ subject to
\begin{align}
y_{i j k\ell} &\le x_{ij} &&\text{for all } i,j,k,\ell\\
y_{i j k\ell} &\le x_{k\ell} &&\text{for all } i,j,k,\ell\\
\sum_{\{i',j',k',\ell'\}=\{i,j,k,\ell\}} y_{i'j'k'\ell'} &\ge 1 &&\text{for all } (i,j,k,\ell)\in Q
\end{align}
For $n = 6$, this minimum is 9.  For general $n \ge 3$, the first several values match $n(n-3)/2$.  Maybe one of the interpretations in OEIS entry A000096 applies.
