In any group of 17 people, where each person knows 4 others, you can find 2 people, which don't know each...
up vote
11
down vote
favorite
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:
combinatorics discrete-mathematics graph-theory
New contributor
add a comment |
up vote
11
down vote
favorite
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:
combinatorics discrete-mathematics graph-theory
New contributor
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
2 days ago
By the way, how did you draw your graphs? Which software did you use? They look very nice.
– Batominovski
2 days ago
1
I used an online tool from there.
– ljaniec
2 days ago
add a comment |
up vote
11
down vote
favorite
up vote
11
down vote
favorite
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:
combinatorics discrete-mathematics graph-theory
New contributor
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:
combinatorics discrete-mathematics graph-theory
combinatorics discrete-mathematics graph-theory
New contributor
New contributor
edited yesterday
Zvi
3,215222
3,215222
New contributor
asked 2 days ago
ljaniec
615
615
New contributor
New contributor
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
2 days ago
By the way, how did you draw your graphs? Which software did you use? They look very nice.
– Batominovski
2 days ago
1
I used an online tool from there.
– ljaniec
2 days ago
add a comment |
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
2 days ago
By the way, how did you draw your graphs? Which software did you use? They look very nice.
– Batominovski
2 days ago
1
I used an online tool from there.
– ljaniec
2 days ago
1
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
2 days ago
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
2 days ago
By the way, how did you draw your graphs? Which software did you use? They look very nice.
– Batominovski
2 days ago
By the way, how did you draw your graphs? Which software did you use? They look very nice.
– Batominovski
2 days ago
1
1
I used an online tool from there.
– ljaniec
2 days ago
I used an online tool from there.
– ljaniec
2 days ago
add a comment |
3 Answers
3
active
oldest
votes
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,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.
Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it!
– ljaniec
2 days ago
1
@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
2 days ago
@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
5 hours ago
@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
4 hours ago
add a comment |
up vote
1
down vote
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
3 hours ago
yes, $N(u,v)$ is defined inside Lemma 1 to be what you said.
– antkam
3 hours ago
Oopps, I didn't see that for some reason. :D
– Batominovski
3 hours ago
add a comment |
up vote
0
down vote
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?
Down vote, what am I missing?
– Phil H
2 days ago
This is an example, not a proof.
– helper
2 days ago
@helper Got it, revised my answer to relay this. A counter example would disprove the theory.
– Phil H
2 days ago
But it's still not an answer, the OP is asking for help proving this.
– helper
2 days ago
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
yesterday
|
show 11 more comments
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
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,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.
Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it!
– ljaniec
2 days ago
1
@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
2 days ago
@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
5 hours ago
@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
4 hours ago
add a comment |
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,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.
Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it!
– ljaniec
2 days ago
1
@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
2 days ago
@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
5 hours ago
@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
4 hours ago
add a comment |
up vote
7
down vote
accepted
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,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.
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.
edited 2 days ago
answered 2 days ago
Batominovski
31.2k23187
31.2k23187
Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it!
– ljaniec
2 days ago
1
@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
2 days ago
@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
5 hours ago
@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
4 hours ago
add a comment |
Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it!
– ljaniec
2 days ago
1
@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
2 days ago
@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
5 hours ago
@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
4 hours ago
Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it!
– ljaniec
2 days ago
Thank you for including links to the additional material, I don't know the used theorem with girth. I will gladly learn it!
– ljaniec
2 days ago
1
1
@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
2 days ago
@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
2 days ago
@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
5 hours ago
@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
5 hours ago
@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
4 hours ago
@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
4 hours ago
add a comment |
up vote
1
down vote
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
3 hours ago
yes, $N(u,v)$ is defined inside Lemma 1 to be what you said.
– antkam
3 hours ago
Oopps, I didn't see that for some reason. :D
– Batominovski
3 hours ago
add a comment |
up vote
1
down vote
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
3 hours ago
yes, $N(u,v)$ is defined inside Lemma 1 to be what you said.
– antkam
3 hours ago
Oopps, I didn't see that for some reason. :D
– Batominovski
3 hours ago
add a comment |
up vote
1
down vote
up vote
1
down vote
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
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
answered 3 hours ago
antkam
1,373112
1,373112
I assume that $N(u,v)$ is the common neighbor of an anti-edge ${u,v}$. The proof looks correct to me. Bravo!
– Batominovski
3 hours ago
yes, $N(u,v)$ is defined inside Lemma 1 to be what you said.
– antkam
3 hours ago
Oopps, I didn't see that for some reason. :D
– Batominovski
3 hours ago
add a comment |
I assume that $N(u,v)$ is the common neighbor of an anti-edge ${u,v}$. The proof looks correct to me. Bravo!
– Batominovski
3 hours ago
yes, $N(u,v)$ is defined inside Lemma 1 to be what you said.
– antkam
3 hours ago
Oopps, I didn't see that for some reason. :D
– Batominovski
3 hours ago
I assume that $N(u,v)$ is the common neighbor of an anti-edge ${u,v}$. The proof looks correct to me. Bravo!
– Batominovski
3 hours ago
I assume that $N(u,v)$ is the common neighbor of an anti-edge ${u,v}$. The proof looks correct to me. Bravo!
– Batominovski
3 hours ago
yes, $N(u,v)$ is defined inside Lemma 1 to be what you said.
– antkam
3 hours ago
yes, $N(u,v)$ is defined inside Lemma 1 to be what you said.
– antkam
3 hours ago
Oopps, I didn't see that for some reason. :D
– Batominovski
3 hours ago
Oopps, I didn't see that for some reason. :D
– Batominovski
3 hours ago
add a comment |
up vote
0
down vote
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?
Down vote, what am I missing?
– Phil H
2 days ago
This is an example, not a proof.
– helper
2 days ago
@helper Got it, revised my answer to relay this. A counter example would disprove the theory.
– Phil H
2 days ago
But it's still not an answer, the OP is asking for help proving this.
– helper
2 days ago
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
yesterday
|
show 11 more comments
up vote
0
down vote
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?
Down vote, what am I missing?
– Phil H
2 days ago
This is an example, not a proof.
– helper
2 days ago
@helper Got it, revised my answer to relay this. A counter example would disprove the theory.
– Phil H
2 days ago
But it's still not an answer, the OP is asking for help proving this.
– helper
2 days ago
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
yesterday
|
show 11 more comments
up vote
0
down vote
up vote
0
down vote
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?
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?
edited yesterday
answered 2 days ago
Phil H
3,8782312
3,8782312
Down vote, what am I missing?
– Phil H
2 days ago
This is an example, not a proof.
– helper
2 days ago
@helper Got it, revised my answer to relay this. A counter example would disprove the theory.
– Phil H
2 days ago
But it's still not an answer, the OP is asking for help proving this.
– helper
2 days ago
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
yesterday
|
show 11 more comments
Down vote, what am I missing?
– Phil H
2 days ago
This is an example, not a proof.
– helper
2 days ago
@helper Got it, revised my answer to relay this. A counter example would disprove the theory.
– Phil H
2 days ago
But it's still not an answer, the OP is asking for help proving this.
– helper
2 days ago
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
yesterday
Down vote, what am I missing?
– Phil H
2 days ago
Down vote, what am I missing?
– Phil H
2 days ago
This is an example, not a proof.
– helper
2 days ago
This is an example, not a proof.
– helper
2 days ago
@helper Got it, revised my answer to relay this. A counter example would disprove the theory.
– Phil H
2 days ago
@helper Got it, revised my answer to relay this. A counter example would disprove the theory.
– Phil H
2 days ago
But it's still not an answer, the OP is asking for help proving this.
– helper
2 days ago
But it's still not an answer, the OP is asking for help proving this.
– helper
2 days ago
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
yesterday
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
yesterday
|
show 11 more comments
ljaniec is a new contributor. Be nice, and check out our Code of Conduct.
ljaniec is a new contributor. Be nice, and check out our Code of Conduct.
ljaniec is a new contributor. Be nice, and check out our Code of Conduct.
ljaniec is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003926%2fin-any-group-of-17-people-where-each-person-knows-4-others-you-can-find-2-peop%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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
2 days ago
By the way, how did you draw your graphs? Which software did you use? They look very nice.
– Batominovski
2 days ago
1
I used an online tool from there.
– ljaniec
2 days ago