Minimum number of handshakes in the party

Question

In a party of $n$ people, certain pairs of people shake hands with each other. In any group of $k$ people, there exists at least one person who shakes hands with all other persons in that group. What is the minimum number of handshakes that can take place at the party?

The problem is inspired from a contest question which I want to solve in general. Here are my attempts in solving the problem:

There are $\binom n k$ possible groups. In each group, the minimum number of handshakes is $k-1$. So, at first I thought the answer should be $(k-1)\binom n k$. But I realized that the maximum number of handshakes is $\binom n 2$. So, I was highly over counting.

Then, I tried for small cases. For $n=4$ and $k=3$, we have $4$ people $A,B,C,D$. And there are $4$ groups of $3$. We take the first group $(A,B,C)$ where $A$ shakes hands with $B$ and $C$. Then in the groups $(A,B,D)$ and $(A,C,D)$, $B$ and $D$ shake hands with $D$. So, we have a total of $4$ handshakes as minimum in this case. From here, I think it's not easy to find the minimum for even small cases.

So, how to solve the problem?

Answer 1

Any person need to shake hand with minimum $(n-1)-(k-2)$ other persons because otherwise we can select $k-1$ people to form a group with this one person and no one in the group will have shook hand with him. So the minimum amount of handshake is;

$$ \frac{1}{2}n\times\left[\left(n-1\right)-\left(k-2\right)\right] $$

Division by $2$ because one handshake is done by $2$ people

Answer 2

Via integer linear programming, here are minimum values for $1 \le k \le n \le 10$: \begin{matrix} n \backslash k & 1 &2 &3 &4 &5 &6 &7 &8 &9 &10 \\ \hline 1 &0 \\ 2 &0 &1 \\ 3 &0 &3 &2 \\ 4 &0 &6 &4 &3 \\ 5 &0 &10 &8 &7 &4 \\ 6 &0 &15 &12 &12 &9 &5 \\ 7 &0 &21 &18 &18 &15 &11 &6 \\ 8 &0 &28 &24 &25 &22 &18 &13 &7 \\ 9 &0 &36 &32 &33 &30 &26 &21 &15 &8 \\ 10 &0 &45 &40 &42 &39 &35 &30 &24 &17 &9 \end{matrix}

Answer 3

This can be done with $\binom n2 - \binom{k-1}{2}$ handshakes: have everyone shake hands except for handshakes between a group of $k-1$ people. Whenever $k$ people are picked, at least one of them is outside that group, and has shaken hands with everyone.

This upper bound matches Rob Pratt's numerical data for $k=2$ (which is a boring case) and for $k=4, 5, \dots, n$.

I conjecture that this upper bound is tight when $k$ is even; for odd $k$, it will eventually be worse than a different bound I outline below, but only when $n$ is sufficiently large (hence it did not yet appear in Rob Pratt's table).

---

This leaves out the $k=3$ case. For $k=3$, we can prove that the optimal number of handshakes is $\lceil \frac12 n(n-2)\rceil = \binom n2 - \lfloor \frac n2\rfloor$.

The lower bound is by Rezha Adrian Tanuharja's argument: every person has to shake hands with at least $n-2$ people, because a person that shook hands with only $n-3$ people can be put in a group of $k=3$ people with the two people whose hands they didn't shake. This gives a lower bound of $\frac12n(n-2)$, which we can round up in the case of odd $n$.

We can match this lower bound in the $k=3$ case! Take all $\binom n2$ handshakes between guests we'll number $1, 2, \dots, n$, and remove the $\lfloor \frac n2\rfloor$ handshakes between the pairs $\{1,2\}$, $\{3,4\}$, $\{5,6\}$, and so on through either $\{n-2,n-1\}$ or $\{n-1,n\}$ depending on parity. Imagine that people $\{2k-1,2k\}$ came to the party together, and don't need to shake hands.

In fact, this construction also works for every odd value of $k$: in any group of odd size, there will be a person in the group whose buddy they came to the party with is not in the group. That person shakes hands with everyone else.

For odd $k$ and sufficiently large $n$, $\binom n2 - \lfloor \frac n2\rfloor$ is better than $\binom n2 - \binom{k-1}{2}$. So the second construction is eventually better than the first.

Answer 4

To prove the conjecture from Misha Lavrov I show that every graph $G=(V,E)$ satisfying the property $E_k$ for an even $k \in \mathbb{N}$ has at least ${n \choose 2} - {k-1 \choose 2}$ edges. (Here, I mean with $E_k$ the property that every subgraph of $G$ of order $k$ contains one vertex that is connected with all others).

To do so, I use that any such graph $G$ with order $n \geq k$ contains one vertex that is connected with every other vertex. Then the claim follows directly, since given $G$ one can enumerate its vertices as $(v_1, \dots, v_n) \subseteq V$ such that $v_i$ shares an edge with every $v_{i+1}, \dots, v_n$ for $1 \leq i \leq n-(k-1)$. (Choose $v_1 \in V$ such that $v_1$ is connected to all other vertices in $V$. Then consider the subgraph $G' \subset G$ obtained by removing $v_1$ and all its edges from $G$. Then $G'$ still satisfies $E_k$ and therefore we can repeat the procedure until there are only $k-1$ vertices left). Thus, there are at least $$ \#E \geq (n-1) + (n-2) + \dots (n-(n-(k-1))) = {n \choose 2} - {k-1 \choose 2}$$ edges in $G$. The identity on the RHS can be shown by induction over $n$.

Now, let me show that $G=(V, E)$ contains one vertex $v_0 \in V$ that is connected to all other vertices. Assume that this is not the case. Then for every $v \in V$ there is some $v^c \in V$ such that $v$ and $v^c$ do not share an edge. We construct sets $V_2, V_4, \dots, V_k \subseteq V$ such that $V_i$ contains $i$ vertices and no vertex in $V_i$ is connected to all others (in $V_i$).

• Choose an arbitrary $v \in V$ and set $V_2 := \{v, v^c\}$.
• Given $V_i \subseteq V$ with the desired properties there are two possibilities: 1) There is some $v \in V \setminus V_i$ such that $v^c \in V \setminus V_i$. Then set $V_{i+2} := V_i \cup \{v, v^c\}$ and neither $v$ nor $v^c$ can be connected to every other vertex in $V_{i+2}$. 2) Otherwise every $v \in V \setminus V_i$ is not connected to some vertex in $V_i$. Therefore, we can set $V_{i+2} := V \cup \{v,w\}$ for two arbitrary $v, w \in V \setminus V_i$ and neither $v$ nor $w$ can be connected to every vertex in $V_i$.

Then the set $V_k$ is a set of $k$ vertices such that no vertex in $V_k$ is connected to every other vertex in $V_k$ - contradicting the fact that $G$ satisfies $E_k$. Thus, the assumption has been false and $G$ contains a vertex which shares an edge with every other vertex in $G$.