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: 1st graph ![secondGraph](https://i.imgur.com/a/Fnbmq7V.jpg)

  • 1
    I do not think that this problem has a simple solution. Any proof will most likely have to prove the non-existence of a Moore graph with girth $5$ and degree $4$. As far as I know, there is no non-algebraic proof. See the pdf file in the link in my answer. – Batominovski Nov 18 at 19:42
  • By the way, how did you draw your graphs? Which software did you use? They look very nice. – Batominovski Nov 18 at 22:34
  • 1
    I used an online tool from there. – ljaniec Nov 18 at 22:47
up vote 7 down vote accepted

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.

  • Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it! – ljaniec Nov 18 at 20:49
  • 2
    @ljaniec This theorem has one of the most unexpected and beautiful proofs I know. So, I am sure that it will benefit you greatly to learn such tricks. – Batominovski Nov 18 at 20:51
  • @Batominovski - the H-S Theorem and the proof are awesome! Every anti-edge $\{u,v\}$ having exactly 1 common neighbor, or equivalently, exactly 1 2-hop path, is such a natural combinatorial description, that it's hard to understand why we need an algebraic proof involving real eigenvalues. Do you have any further insight into why there is no combinatorial proof? – antkam Nov 20 at 19:01
  • @antkam I think the main difficulty is exactly how to combinatorially use the condition that there exists exactly one $2$-hop path between two nonadjacent nodes. It is much easier to approach the problem using the adjacency matrix as you can see in the pdf file. But when we start to use the adjacency matrix, our solution becomes at least partially algebraic. And when you look at the result, the numbers $1$, $2$, $3$, $7$, and $57$ are very arbitrary, so it doesn't seem very likely to me that you can approach the problem from a purely combinatorial point of view. – Batominovski Nov 20 at 20:32
  • Is this possible to solve with linear algebra aproach? – greedoid Dec 1 at 18:03

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

  • I assume that $N(u,v)$ is the common neighbor of an anti-edge $\{u,v\}$. The proof looks correct to me. Bravo! – Batominovski Nov 20 at 21:23
  • yes, $N(u,v)$ is defined inside Lemma 1 to be what you said. – antkam Nov 20 at 21:24
  • Oopps, I didn't see that for some reason. :D – Batominovski Nov 20 at 21:24
  • @antkam It was kind of thinking I had before, but I couldn't summarize it as well as you, thank you! – ljaniec Nov 21 at 1:47
  • 1
    @ljaniec i know exactly what you mean. it was really tedious until i found the 3x3 grid which helped me tremendously with the visualization of symmetries. Batominovski's "no triangles and no quads" also provides a great rule of thumb. – antkam Nov 21 at 5:19

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

enter image description here

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?

enter image description here

  • Down vote, what am I missing? – Phil H Nov 18 at 19:50
  • This is an example, not a proof. – helper Nov 18 at 19:52
  • @helper Got it, revised my answer to relay this. A counter example would disprove the theory. – Phil H Nov 18 at 19:54
  • But it's still not an answer, the OP is asking for help proving this. – helper Nov 18 at 19:55
  • It is correct that 6,7,8 (who each knows 3) collectively have to know 9-17, but there is no reason to link 6 with 9-11. in fact, since 6 must be only 2-hops from 2,4,5, this means 6 must link with exactly 1 of 9-11, 1 of 12-14 and 1 of 15-17. suppose WOLOG 6 links with 9,12,15, then 6 must reach 10,11 via 12,15. etc. the challenge is to show that this is impossible to satisfy for everybody. – antkam Nov 19 at 19:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.