+0  
 
0
147
7
avatar

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
 #1
avatar
0

any help?

Guest Jul 1, 2018
 #2
avatar+93866 
0

I'd like to see someone answer the second question too :)

---

I do not think I can help with the second question. 

And I do not even understand what you are asking with the first question. (That may or may not be because of my own ignorance)

Melody  Jul 2, 2018
edited by Melody  Jul 2, 2018
 #3
avatar
+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 smiley

Guest Jul 2, 2018
 #4
avatar+93866 
0

Thanks Guest :)

Melody  Jul 2, 2018
 #7
avatar
0

120 is wrong

Guest Jul 2, 2018
 #5
avatar+27128 
+1

Here's a graph that conforms to the specified vertices:

 

I know little or nothing about graph theory, so I wrote a brute force and ignorance program to calculate the number of paths of length 2 here and came up with 77.  However, it wouldn't surprise me if this were wrong!

Alan  Jul 2, 2018
 #6
avatar+93866 
0

Looks interesting :)

Melody  Jul 2, 2018

40 Online Users

avatar
avatar
avatar
avatar
avatar
avatar
avatar
avatar
avatar
avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.