There are 70 people in a group of people $P$. Each of them sent messages to at least 36 other people of the group. Let's $G = \{X \in P~|~\nexists Y \in P~\text{such that $X$ and $Y$ both sent messages to each other}\}$. It turned out that $|G| = 55$. Let's $G' = P \setminus G$. Prove that in $G'$ every pair of people sent messages to each other.
From the problem statement it's clear that we should prove that $G'$ is a complete graph. I tried to prove it by contradiction. Let's suppose in $G'$ there is a pair of people such that at least one of them didn't sent message to the other. I'm struggling to find how to move further with this logic.
Any help, suggestions and ideas how to solve the problem would be greatly appreciated.
The total number of edges is $|P| \cdot 36$. The maximum number of edges from $G$ to $G$ is ${|G| \cdot (|G|-1) \over 2}$ (only one edge between each pair). By the same observation, there are at most $|G| \cdot (|P|-|G|)$ edges between $F$ and $P \setminus G$. Hence there are at least $36 |P| - {|G| (G| - 1) \over 2} - |P| (|P| - |G|) = 210$ edges from $P \setminus G$ to $P \setminus G$. Since $|P \setminus G| = 15$ this is possible only if $P \setminus G$ is a clique.
Update: the rest of the answer was relevant without the constraint $|G|=55$.
Hm, it seems to be false. Consider the following graph: let $V$ be a set that will become $G$ and $U$ be its complement. $|V|=|U|=35$. Let $V = \{v_0, \ldots, v_{34}\}$, $U = \{u_0, \ldots, u_{34}\}$.
Add all edges from $U \times U$ except loops and the edge $u_0 \to u_1$. For all $v_i$ add edges to $v_{(i+1) \bmod 35}, v_{(i+2) \bmod 35}, \ldots, v_{(i+17)\bmod 35}, u_i, u_{(i+1) \bmod 35}, \ldots, u_{(i+19) \bmod 35}$. For each $u_i$ add edges $u_i \to v_{(i+1) \bmod 35}$ and $u_i \to v_{(i+2) \bmod 35}$. Also add edge $u_0 \to v_3$.
For any $v \in V$ there is no $w \in U \cup V$ such that $v \to w$ and $w \to v$ are both edges of the graph. But $U$ does not induce a complete graph.