Can we always find pairs of intersecting subsets? This simple-to-state question has been bugging me the whole day: Consider a set $S$ of $2n$ elements and let $F$ be the family of all $k$-size subsets of $S$, for some $1 < k \le n$.
Question: Is it possible to pair-up the sets in $F$ such that each pair has a nonempty intersection? (If $|F|$ is odd, we allow one set to be paired with itself.)
 A: Actually, I think the comment of ajr provides the idea for a proof of the general case. In particular, we can explicitely construct a list of the subsets with the additional property that any two consecutive elements have a non-empty intersection. Then, a greedy grouping of elements along this list will do.
Let $n >= 2$ and fix $k$ such that $1 < k <=n$. Wlog, let $S = \{1, 2, ..., 2n \}$ and consider the set $F$ of all $k$-subsets of $S$.
We define $F_1 = \{ f \in F : 1 \in f \}$ and $F_i = \{ f \in F : 1, \dots, i - 1 \notin F, i \in F \}$ for all $2 <= i <= 2n - k + 1$. Notice that for all $1 <= i <= 2n - k + 1$ we have that $F_i$ is non-empty. Moreover, all $F_i$'s are disjoint but together make up all of $F$. Additionally, for all $1 <= i < 2n - k + 1$ the set $F_i$ contains distinct elements $f_i^{i + 1} \neq f_i^{2n}$ such that $i + 1 \in f_i^{i + 1}$ and $2n \in f_i^{2n}$. The set $F_{2n - k + 1}$ contains a single element $f_{2n - k + 1}^{2n -k + 2} = f_{2n - k + 1}^{2n} = \{2n - k + 1, 2n -k + 2, \dots, 2n\}$.
Now consider listing all elements from $F_1$ from $f_1^2$ to $f_1^{2n}$. Append to that list all elements from $F_2$ starting from $f_2^{2n}$ to $f_2^3$. Next, all elements from $F_3$ starting from $f_3^4$ to $f_3^{2n}$. Continue in this alternating fashion to obtain a list $L$ of all items in $F$. Notice now that any two consecutive elements $l_p, l_{p + 1}$ in this list $L$ have non-empty intersection: If they both belong to the same $F_i$ then they share the number $i$. Otherwise, our construction guarantees that they either share the number $i + 1$ (where $l_p \in F_i$) or $2n$.
Since any two consecutive elements have non-empty intersection, we can group consecutive elements together greedily starting at the beginning of $L$.
Of course this could also be formulated in graph-theory terms: We explicitely constructed a Hamiltonian path in the graph where vertices correspond to $k$-subsets and edges exists between vertices with non-empty intersection. Of course, such a Hamiltonian path directly yields the desired nearly-perfect matching.
