I am really bad at graph theory, how do you do this problem?

One more question: If there is a room with 100 people, and each person knows 67 others, how do you prove that there are 4 people who know each other? Knowing is mutual, where if A knows B, then B knows A.

Thank you

Guest Jul 1, 2018

#3**+1 **

Answer to the first question:a path of length 2 consists of 3 ordered vetrices, where the first vetrice is connected to the second, and the second vertice is connected to the third (the first vetrice and the third vertice can't be the same vetrice).

In a path of length 2, the second vertice has to be connected to at least 2 other vertices, meaning that the second vetrice's degree has to be at least 2. suppose we have a vetrice v, deg(v)=r>1, to find the number of paths of length 2 where the second vertice is v, we have to find the number of vertices that are connected to v (that's r, by definition) and multiply it by r-1 (so, if we have a vertice with degree r, the number of paths of length 2 where the second vertice is v is r(r-1)).

why? we already know that the second vertice is v, all we have to do is find other 2 vertices, that are connected to the second one. the order of the vertices matters, because one has to be the first vertice (where the path begins) and one has to be the last vertice (where the path ends). we have r vertices to choose from, so we have a total number of r(r-1) combinations.

to find the total number of paths with length 2, we have to find deg(v)*(deg(v)-1) for every vertice v with deg(v)>1, and find the sum of the results.

so the answer should be 2*(2-1)+3*(3-1)+3*(3-1)+3*(3-1)+4*(4-1)+4*(4-1)+5*(5-1)+8*(8-1)=2+6+6+6+12+12+20+56=120

i hope im right

Guest Jul 2, 2018