Nsryjdtyk

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:

Let $G(V,E)$ be a $4$-regular simple graph on $17$ vertices. We claim that there are two vertices $u,vin V$ such that $uneq 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},wbig)$ with $u,v,win V$ such that $uneq v$, ${u,v}notin E$, and $w$ is adjacent to both $u$ and $v$. For each $win 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{4cdot |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 $win 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 $ggeq 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 $rin{1,2,3,7,57}$ (we know a partial converse, that is, for $rin{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.

EDIT: I submitted a less than helpful response the first time. Here is my proof in this edit.

When all $17$ people within a group know $4$ people from the group, then there are $34$ friend pairings.
In the above diagram, ensuring that everyone is at least a friend of a friend requires $52$ pairings "so far" just for persons $1$ through $5$. I have only worked the requirement for persons $1$ to $5$ because it already exceeds the requirement of knowing exactly $4$ others.

Every person in the group doesn’t personally know $12$ others in the group. But for there to be a possibility of sharing a friend with all $12$ others, every person’s $4$ friends must between them know all the other $12$.

In the diagram above, person $1$ personally knows $4$ others $(2,3,4,5)$. And between this $4$, they know all the other $12$ people ($6$ through $17$). But the same situation must exist for the friends of $1$, ($2,3,4$ and $5$). So, on the chart this requirement has been filled in where each set of $4$ friends for $2,3,4,5$ must know their corresponding other $12$. When this is done however, the number of friends for some of the people exceeds $4$. Not only that, but ensuring everyone is a least a friend of a friend hasn't been done for all $17$ in the group.

These are the $5$ acquaintance pairings so far:

$17 (8,11,12,13,14); 12 (6,7,8,10,17); 7(9,12,13,14,15)$

$16 (8,9,10,11,14); 11 (6,13,15,16,17); 6 (9,10,11,12,15)$

$15 (6,7,8,11,14); 10 (6,12,13,14,16)$

$14 (7,10,15,16,17); 9 (6,7,8,13,16)$

$13 (7,9,10,11,17); 8 (9,12,15,16,17)$

Therefore, for all unacquainted people to share a common friend, the unacquainted people have to know more than $4$ people. Hence with each person only knowing $4$ others, there will always be at least two people who don’t know each other and do not share a common friend.

A follow up question could be, what is the least number of acquaintances each person must have to ensure that everyone is at least a friend of a friend?