I have a problem with proof of this (graph theory):
In any group of 17 people, where each person knows exactly 4 people, you can
find 2 people, which don't know each other and have no common friends.
I translated this to proving, that there exists a pair of vertices $\{v,w\}$, which aren't connected, that is, there isn't edge $(v,w)$ and for any other vertex $x$ from $V$ applies $(x, v) \veebar (x, w)$ or there is no edges between $x$ and $v$ and between $x$ and $w$, but then I am stuck.
I tried using Pigeonhole Principle, but I couldn't use it correctly, I think. I couldn't use Ramsey theory too.
Any help and hints would be appreciated.
I drew two examples of these graphs for help:
](https://i.stack.imgur.com/2N0Hn.png)
Best Answer
Let $G(V,E)$ be a $4$-regular simple graph on $17$ vertices. We claim that there are two vertices $u,v\in V$ such that $u\neq v$, $u$ is not adjacent to $v$, and $u$ and $v$ do not have a common neighbor. We prove by contradiction by assuming that, for any two distinct vertices $u$ and $v$ of $G$, if $u$ is not adjacent to $v$, then $u$ and $v$ have a common neighbor.
Let $S$ denote all pairs $\big(\{u,v\},w\big)$ with $u,v,w\in V$ such that $u\neq v$, $\{u,v\}\notin E$, and $w$ is adjacent to both $u$ and $v$. For each $w\in V$, $w$ has four neighbors. Therefore, at most $\binom{4}{2}$ pairs of neighbors of $w$ are not adjacent. This proves that $$|S|\leq \binom{4}{2}\,|V|=6\,|V|=102\,.\tag{*}$$
Now, $|E|=\dfrac{4\cdot |V|}{2}=2\,|V|=34$ by the Handshake Lemma. Thus, there are $$\binom{17}{2}-|E|=102$$ pairs of vertices $\{u,v\}$ that are not edges of $G$. Each anti-edge pair $\{u,v\}$ produces at least one element of $S$, due to our hypothesis on $G$. This proves that $$|S|\geq 102\,.\tag{#}$$
From (*) and (#), we must have $|S|=102$. For (#) to be an equality, every anti-edge pair $\{u,v\}$ must have exactly one common neighbor $w\in V$. Additionally, $G$ must be a triangle-free graph for (*) to become an equality. This means $G$ is both triangle-free and quadrilateral-free. Therefore, $G$ is a graph on $17=4^2+1$ vertices with girth $g\geq 5$ in which all vertices have degree $4$. By the Hoffman-Singleton Theorem (for a proof, see here), if there exists an $r$-regular simple graph on $r^2+1$ vertices with girth at least $5$, then $r\in\{1,2,3,7,57\}$ (we know a partial converse, that is, for $r\in\{1,2,3,7\}$, there exists such a graph, but it is still a mystery for $r=57$, as you may guess, it is not easy to construct a graph on $57^2+1=3250$ vertices). This yields the desired contradiction.