In a party attended by $2015$ guests among any $5$ guests at most $6$ handshakes had been exchanged. Determine the maximal number of handshakes.

Question

In a party attended by $2015$ guests among any $5$ guests at most $6$ handshakes had been exchanged. Determine the maximal possible number of handshakes.

Turkey EGMO TST 2015 P6

Some findings:

• Say we have $m$ handshakes. If we connect every 5 tuple with edges in it we get $${2015 \choose 5}\cdot 6\geq m\cdot {2013 \choose 3} \implies m\leq 1209\cdot 1007$$
• If we observe $H:=\bar{G}$ instead of $G$ then among any five we have at least 4 edges. Say $H$ has conected components $C_1,...,C_k$, then $k\leq 2$ since else we don't necessary get $4$ edges.
  • If $k=2$ then $C_1$ and $C_2$ must be clique, since however we take 2 vertices $u,v$ in one component (and 3 vertices in other component), they must be connected in order to get 4 edges in total of five vertices. So $G$ is complete bipartite graph and we have $m\leq 1007\cdot 1008$.
  • If $k=1$, then $H$ is connected and now...?

Answer 1

We work in $H$ the complement of $G$ which has $m'$ edges. So among any 5 we have at least 4 edges.

Here is an idea, we can ask how many edges are there in a subset with $7$ vertices? The answer is $9$ and then we proceede, what about in a set of $9$ vertices? The answer is $16$, and so on. So we can prove a following lemma.

Lemma: In any set with $2n+1$ vertices we have at least $n^2$ edges in $H$.

Proof: With induction on $n$. In a set $S$ with $2n+3$ vertices we have ${2n+3\choose 2n+1}$ subsets with $2n+1$ vertices and any of it has at least $n^2$ edges. Let $S$ have $k$ edges. Then we have $$ {2n+3\choose 2n+1} \cdot n^2\leq k\cdot {2n+1\choose 2n-1} \implies k\geq (n+1)^2$$

---

So when $n=1007$ we get $k=m'\geq 1007^2$ so $$m\leq {2015\choose 2} -1007^2 = 1007\cdot 1008$$ which is achiavable with $G= K_{1007,1008}$.

Answer 2

Consider a graph $G(V,E)$ representing, as usual, the members who attended the party as vertices, and the exchanged handshakes as edges. Let, furthermore, $\lvert V(G) \rvert=n$ be the number of members, and $M(n)$ be the maximal possible number of edges under the given condition. Also, in order to avoid any sort of confusion, I will employ $\deg(a)$ in order to denote the degree of a vertex $a\in V(G)$ in $G$, and $d(a)$ in order to denote the degree of a vertex $a\in V(G_1)$ in the subgraph $G_1$ mentioned later on.

Claim.

• For $n=2k$, we have $M(n)=k^2$

• For $n=2k+1$, we have $M(n)=k\cdot (k+1)$

We will induct on the number of edges. For $n=5=2\cdot 2+1$, it is obvious that we will have $M(6)=6=3\cdot 2.$

$\color{blue}{\textbf{Case 1. }}$ Take $n=2k$ and assume that $M(2k-1)=k\cdot (k-1)$. Let $v\in V(G)$ be the vertex with the lowest degree in $G$. Consider now the subgraph $G_1$ formed by leaving $v$ and its edges out of $G$. The induction hypothesis yields $\lvert E(G_1)\rvert \leqslant k\cdot (k-1)$.

Since we are looking for $M(2k)$, we will assume that $\lvert E(G_1)\rvert = k\cdot (k-1)$ and aim to maximize $\deg(v)$ (see remark at the end). Since $v$ is defined to be the vertex with the lowest degree in $G$, we want the smallest degree in $G_1$ to be as high as possible. Due to $\sum _{u\in V(G_1)}d(u)=2k\cdot (k-1)$, we will achieve this letting $d(u)\in \left\{\left\lfloor\frac{2k\cdot (k-1)}{2k-1}\right\rfloor, \left\lceil\frac{2k\cdot (k-1)}{2k-1}\right\rceil\right\}\iff d(u)\in \{k-1, k\}$ for every $u\in V(G_1).$ Thus, for $k-1$ vertices of $a\in V(G_1)$, one obtains $d(a)=k$, and for the $k$ remaining vertices $b\in V(G_1)$, one obtains $d(b)=k-1$. Finally, we obviously have $\deg(v)\leqslant k$, where $\deg(v)=k$ can be achieved if every vertex $b\in V(G_1)$ with $d(b)=k-1$ is adjacent to $v$ in $G$, i.e. if every vertex in $V(G)$ has degree $k$. This, altogether, yields $\sum_{c\in V(G)}\deg(c)=2k^2\implies \lvert E(G)\rvert =k^2$. Taking $G=K_{k,k}$ should do the trick.

$\color{blue}{\textbf{Case 2. }}$ This can be handled in a similar spirit. Take $n=2k+1$ and assume that $M(2k)=k^2$. Let $v\in V(G)$ be the vertex with the lowest degree in $G$. Consider now the subgraph $G_1$ formed by leaving $v$ and its edges out of $G$. The induction hypothesis yields $\lvert E(G_1)\rvert \leqslant k^2$.

Since we are looking for $M(2k+1)$, we will assume that $\lvert E(G_1)\rvert = k^2$ and aim to maximize $\deg(v)$ (see remark at the end). Since $v$ is defined to be the vertex with the lowest degree in $G$, we want the smallest degree in $G_1$ to be as high as possible. Due to $\sum _{u\in V(G_1)}d(u)=2k^2$, we will achieve this letting $d(u)\in \left\{\left\lfloor\frac{2k^2}{2k}\right\rfloor, \left\lceil\frac{2k^2}{2k}\right\rceil\right\}\iff d(u)=k$ for every $u\in V(G_1).$ Finally, we obviously have $\deg(v)\leqslant k$, where $\deg(v)=k$ can be achieved if, in $G$, $k$ vertices have degree $k+1$ and $k+1$ vertices have degree $k$. This, altogether, yields $\sum_{c\in V(G)}\deg(c)=2k\cdot (k+1)\implies \lvert E(G)\rvert =k\cdot (k+1)$. Taking $G=K_{k,k+1}$ should do the trick.

Remark. One could argue that letting $\lvert E(G_1)\rvert$ be smaller, one could achieve a higher $\deg(v)$. But it is easy to confirm that this is false, as $\deg(v)\leqslant d(u)-1$ for every $u\in V(G_1)$.