In any group of 17 people, where each person knows 4 others, you can find 2 people, which don't know each other and have no common friends.

Question

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:

Answer 1

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.

Answer 2

Here is an extremely tedious combinatorial proof... :P It works for this case but most likely cannot generalize.

Lemma 1: The following are taken from the first part of the answer by @Batominovski

• The graph $G$ is triangle-free and quadrilateral-free.

• If $(u,v)$ is not an edge then $u, v$ have exactly 1 common neighbor, which we will denote $N(u,v)$.

Let the nodes be $\{1, 2, ..., 17\}$. The following tables show successive "forced" constructions of the adjacency matrix in "sparse format", i.e. a row "a: b, c, d, e" means there are edges a-b, a-c, a-d and a-e.

WOLOG we can pick node 1 and choose its 4 neighbors and their neighbors, to start:

 1:  2  3  4  5
 2:  1  6  7  8
 3:  1  9 10 11
 4:  1 12 13 14
 5:  1 15 16 17

Now consider nodes $\{6,7,...,17\}$ organized into 4 triplets $T_i: i \in \{2,3,4,5\}$ where each $T_i =$ the 3 nodes (among 6...17) connected to $i$. E.g. $T_3 = \{9,10,11\}$.

Lemma 2: For $i \neq j: \{N(u,j): u \in T_i\} = T_j$, i.e. the function $N(.,j)$ is bijective from $T_i$ to $T_j$.

Proof: first of all $N(u,j) \in T_j$ because there is no other way to connect to $j$. (The only other neighbor of $j$ is $1$ which does not connect to $u$.) Next $u \neq u' \implies N(u,j) \neq N(u',j)$ because otherwise $(N(u,j), u, i, u', N(u',j))$ would be a quadrilateral.

Based on Lemma 2, WOLOG we can fill out the neighbors of every $u \in T_2$:

 6:  2  9 12 15
 7:  2 10 13 16
 8:  2 11 14 17

At this point we arrange the remaining nodes 9...17 and visualize them in a 3x3 grid:

   9   10   11  .. [3]
  12   13   14  .. [4]
  15   16   17  .. [5]
   :    :    :
  [6]  [7]  [8]

The 3 nodes of any given row have a common neighbor (3, 4 or 5, in []) and the 3 nodes of any given column also have a common neighbor (6, 7, 8, in []).

Node 13 still has 2 edges left. It cannot connect to 12/14 on the same row (13-12/14-4-13 triangle) nor 10/16 on the same column. The 2 edges must also connect to different columns (e.g. 13-9 & 13-15 would lead to 13-9-6-15-13 quadrilateral) and different rows. WOLOG we connect 9-13 and 13-17.

   9   10   11  .. [3]
     \
  12   13   14  .. [4]
          \
  15   16   17  .. [5]
   :    :    :
  [6]  [7]  [8]

Now after connecting 9-13, node 9 has 1 edge left. This cannot connect to 10/11 (same row as 9), nor 12/15 (same column), nor 16 (9-16-7-13-9 quad) nor 14 (9-14-4-13-9 quad), so it must connect to 17. But this forms a triangle 9-13-17-9, a contradiction.

Whew... and yuck. :P

Answer 3

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?