What's the minimal $k$ satisfying these conditions? Graph theory problem.

Question

I'm thinking following problem.

There are five pairs of couples (So, ten people total) and $k$ clubs satisfying following three conditions. Let $A,B$ are arbitrary people among those 10,

1. If $A$ and $B$ are a couple, they never belong to same club.
2. If $A$ and $B$ are two people and not a couple, exactly one club contains both of them.
3. There exists at least one person that belongs to exactly two clubs.

What is the minimum number $k$ satisfying above conditions?

I believe the graph theoretic interpretation is useful to solve this problem. To get some intuition, I tried three couples case. and it seems minimal $k$ is $4$, I think. but for the case of five couples, I still don't know. Is there any systematic way to approach these kinds of problems? Also, can we solve above problem for arbitrary $n$ couples case?

Answer 1

The answer is $\mathbf{k = 14}$.

Consider the more general question where the number of couples is a parameter. In the case of just one couple the minimal system has $k=3$, with one person belonging to two clubs, and the other person belonging to a different club. Therefore suppose there are $n\ge 2$ couples.

Condition 3 implies that there is some person $u$ in precisely two clubs $C$ and $D$. Suppose $v$ is some person not in $C$ or $D$; in particular, $v\ne u$. By condition $2$, if $v$ and $u$ are not a couple, then they must be in some club in common, so $v\in C$ or $v\in D$, a contradiction. Hence $v$ is the unique partner of $u$. It follows that $C$ and $D$ have $2n-1$ members between them. By condition 2 the unique member common to both $C$ and $D$ is $u$. Moreover, no club can have more than $n$ members by condition 1 and the pigeonhole principle. Hence both $C$ and $D$ have exactly $n$ members.

Now consider two people $x\in C\setminus \{u\}$, $y\in D\setminus \{u\}$. If $x$ and $y$ are a couple then there must be some clubs $E_{xv|y}$ and $E_{yv|x}$ such that $x\in E_{xv|y}$ and $y\in E_{yv|x}$, and (by condition 2) clubs $E_{xv|y}$, $E_{yv|x}$, $C$, and $D$ must be pairwise distinct. Otherwise $x$ and $y$ are not a couple, and by condition 2 there must be some club $C_{xy}$ in which both $x$ and $y$ are members. Now $C_{xy}$, $C$, and $D$ must be pairwise distinct clubs, and $u\not\in C_{xy}$ by condition 2. Suppose $w \in C_{xy}\setminus \{x,y\}$. By condition 2, $w\not\in C$ and also $w\not\in D$, so $w=v$. This means that the clubs $C_{xy}$ either contain only $x$ and $y$, or contain $x$, $y$, and $v$ and no other members. Since there must be a club $C_{xy}$ for each $x\in C\setminus \{u\}$ and $y\in D\setminus \{u\}$ that are not partners, there are at least $(n-1)(n-2)$ such clubs.

If $n=2$ then there are no such clubs $C_{xy}$, but denoting the other couple by $x,y$, there are at least the four distinct clubs $C$, $D$, $E_{xv|y}$, and $E_{yv|x}$. This can be achieved with $k=4$ clubs that each have precisely two of the people as members. So now suppose $n\ge 3$, when there exist some such clubs $C_{xy}$. Then there must be at least $(n-1)(n-2)+2$ clubs. Now let $C_{xy}=\{x,y\}$ for each $x \in C\setminus \{u\}$ and $y \in D\setminus \{u\}$ that are not a couple. Now pick a set of pairs $\{(x_1,y_1),(x_2,y_2),\dots,(x_{n-1},y_{n-1})\} \subseteq (C\setminus \{u\})\times (D\setminus\{u\})$ such that $\{u,x_1,x_2,\dots,x_{n-1},y_1,y_2,\dots,y_{n-1}\} = C\cup D$ and $x_i,y_i$ are not a couple for any $i = 1,2,\dots n-1$, and add $v$ to $C_{x_i y_i}$ for each $i=1,2,\dots,n-1$. There are precisely $(n-1)(n-2)+2$ such clubs, and these satisfy all three conditions. Hence this system achieves the smallest possible $k$ and has $(n-1)(n-2)+2$ clubs.

In the case $n=5$ this is $k = 14$ clubs; in this system $u$ is a member of two clubs with $5$ members each, $v$ belongs to four clubs with three members each, and the other $8$ people belong to four clubs each, one with $5$ members and three with three, one with three, and two with two.

Thanks to @bof for pointing out an error in the witness I was proposing for the upper bound, and to @browngreen for an error in the final summary; the parts in italics indicate the fix.

Answer 2

I would go about this problem in the following way:

Let $A$ be the person who is in exactly 2 clubs (which we can call $Club1$ and $Club2$), and let $B$ be the couple partner of $A$. Since $A$ must be in exactly one club with every person other than B, the remaining 8 people must each belong to exactly one of $A$'s 2 clubs. Furthermore, since those 8 people consist of 4 couples, they must be divided 4 and 4, such that one member of each couple is in $Club1$ and the other member of each couple is in $Club2$.

Now each of the 4 people in $Club1$ (other than $A$) must still be in a club with each of the 4 non-$A$ people in $Club2$ other than their partner. But since none of the $Club1$ members can be in any more clubs together, nor can any of the $Club2$ members be in any more clubs together, each of the 4 $Club1$ members will have to form individual clubs to be with each of the 3 non-partner non-$A$ members in $Club2$. This creates 12 additional clubs.

The only thing left is that $B$ needs to be in a club with each of the other 8 people (besides for $A$). However, this can be done without creating any additional clubs. $B$ can join 4 of the aforementioned 12 clubs in such a way that they will be with each of the 8 people exactly once. For example, if we call the $Club1$ members $X_1,X_2,X_3,X_4$ and the $Club2$ members $Y_1,Y_2,Y_3,Y_4$ with the corresponding numbers being the couples, $B$ can join the clubs $(X_1,Y_2),(X_2,Y_3),(X_3,Y_4),(X_4,Y_1)$.

Therefore, we end up with a total of 14 groups, and 14 is the minimum value of $k$.

For a more general solution with $n$ couples, you can use the same method. $A$ will be in 2 clubs, each with $n-1$ other people. Assuming $n-1$ is at least 2, then each of the $n-1$ people from $Club1$ will form a club with each of the $n-2$ people from $Club2$ that are not their partner and not $A$, creating $(n-1)(n-2)$ additional clubs. $B$ can then join $n-1$ clubs in a way that they are with everyone (besides $A$) exactly once, without creating any new clubs. (This can always be done by joining the clubs $(X_1,Y_2),(X_2,Y_3),...,(X_{n-1},Y_n),(X_n,Y_1).)$

Therefore the general solution for $n\ge2$ couples is: minimum $k=2+(n-1)(n-2)$

When there are exactly 2 couples $A$ will still be in 2 clubs (with $X$ and with $Y$) but since $X$ and $Y$ can't form a club together, $B$ will have to be in two separate clubs, one with $X$ and one with $Y$, giving a total of 4 clubs.