# Thread: Graph Theory Question

2. ## Re: Graph Theory Question

Have you looked at how many "friends" each pair has in common? Lets call the three people making up the top triangle "A", "B", and "C" where "A" is the top vertex and we go counter-clockwise so that "C" is that vertex with all 4 other people as friends. Call the last two "D" and "E" again going counter-clockwise around that lower triangle. Now, who are each persons friends?
A has B and C as friends
B has A and C as friends
C has A, B, D, and E as friends
D has C and E as friends
E has C and D as friends

Now look at the 10 pairs:
A and B have C as a common friend
A and C have B as a common friend
A and D have C as a common friend
A and E have C as a common friend
B and C has A as a common friend
B and D have C as a common friend
B and E have C as a common friend
C and D have E as a common friend
C and E have D as a common friend
D and E have C as a common friend

3. ## Re: Graph Theory Question Originally Posted by HallsofIvy Have you looked at how many "friends" each pair has in common? Lets call the three people making up the top triangle "A", "B", and "C" where "A" is the top vertex and we go counter-clockwise so that "C" is that vertex with all 4 other people as friends. Call the last two "D" and "E" again going counter-clockwise around that lower triangle. Now, who are each persons friends?
A has B and C as friends
B has A and C as friends
C has A, B, D, and E as friends
D has C and E as friends
E has C and D as friends

Now look at the 10 pairs:
A and B have C as a common friend
A and C have B as a common friend
A and D have C as a common friend
A and E have C as a common friend
B and C has A as a common friend
B and D have C as a common friend
B and E have C as a common friend
C and D have E as a common friend
C and E have D as a common friend
D and E have C as a common friend
This is how i thought of it:  Is this right?

Here's the graph 4. ## Re: Graph Theory Question

You justified that the solution shown is a possible solution. You have not justified that it is the only solution. There are 10 possible edges in the graph. There are $2^{10} = 1024$ possible graphs on five vertices. That is a finite collection of graphs. You want to show that only the graphs that look like your drawing fit the criteria that any two vertices have edges to exactly one common vertex. Out of the 1024 graphs, I believe 120 of them look like the graph you show as the solution. So, do you really need to "fully justify" it? That might be a considerably larger amount of work. You could justify it by analyzing all of the 1024 graphs and showing that only the 120 graphs that look like the graph shown as a solution are correct. Or, you can assume that you have a valid graph representing this group of five friends and start analyzing it.

Choose two people. Label them A,B. We know they share exactly one friend in common. Call that friend C. We now have edges AC and BC. If we consider A and C, we know they share exactly one friend. So, we have the following possibilities:
Case 1: B is the common friend
Case 2: D is the common friend
Case 3: E is the common friend

Then consider B and C.
Case 1: A is the common friend
Case 2: D is the common friend
Case 3: E is the common friend.

Keep going until you fully explain the entire graph and all possible permutations.

5. ## Re: Graph Theory Question Originally Posted by SlipEternal You justified that the solution shown is a possible solution. You have not justified that it is the only solution. There are 10 possible edges in the graph. There are $2^{10} = 1024$ possible graphs on five vertices. That is a finite collection of graphs. You want to show that only the graphs that look like your drawing fit the criteria that any two vertices have edges to exactly one common vertex. Out of the 1024 graphs, I believe 120 of them look like the graph you show as the solution. So, do you really need to "fully justify" it? That might be a considerably larger amount of work. You could justify it by analyzing all of the 1024 graphs and showing that only the 120 graphs that look like the graph shown as a solution are correct. Or, you can assume that you have a valid graph representing this group of five friends and start analyzing it.

Choose two people. Label them A,B. We know they share exactly one friend in common. Call that friend C. We now have edges AC and BC. If we consider A and C, we know they share exactly one friend. So, we have the following possibilities:
Case 1: B is the common friend
Case 2: D is the common friend
Case 3: E is the common friend

Then consider B and C.
Case 1: A is the common friend
Case 2: D is the common friend
Case 3: E is the common friend.

Keep going until you fully explain the entire graph and all possible permutations.
How would you analyse the graph i'm stuck

6. ## Re: Graph Theory Question Originally Posted by SlipEternal You justified that the solution shown is a possible solution. You have not justified that it is the only solution. There are 10 possible edges in the graph. There are $2^{10} = 1024$ possible graphs on five vertices. That is a finite collection of graphs. You want to show that only the graphs that look like your drawing fit the criteria that any two vertices have edges to exactly one common vertex. Out of the 1024 graphs, I believe 120 of them look like the graph you show as the solution. So, do you really need to "fully justify" it? That might be a considerably larger amount of work. You could justify it by analyzing all of the 1024 graphs and showing that only the 120 graphs that look like the graph shown as a solution are correct. Or, you can assume that you have a valid graph representing this group of five friends and start analyzing it.

Choose two people. Label them A,B. We know they share exactly one friend in common. Call that friend C. We now have edges AC and BC. If we consider A and C, we know they share exactly one friend. So, we have the following possibilities:
Case 1: B is the common friend
Case 2: D is the common friend
Case 3: E is the common friend

Then consider B and C.
Case 1: A is the common friend
Case 2: D is the common friend
Case 3: E is the common friend.

Keep going until you fully explain the entire graph and all possible permutations.
How do you know 120 of them look like that?

7. ## Re: Graph Theory Question

We have A,B have C as their only common friend. Now, we are looking at A and C.
Case 1: B is the common friend. Now we have edges AB, AC, and BC.
Case 2: D is the common friend. Now we have edges AC, BC, AD, CD.
Case 3: E is the common friend. Now we have edges AC, BC, AE, CE.

Next, consider A and D.
Case 1,1: B is the common friend. Then we have edges AB, AC, BC, BD. This is a problem because A and B have two common friends (C and D), so this is not possible.
Case 1,2: C is the common friend. Then we have edges AB, AC, BC, CD. This is fine.
Case 1,3: E is the common friend. Then we have edges AB, AC, BC, AE, DE. This is fine.
Case 2,1: Given the edges AC, BC, AD, CD, we already have C as a common friend for A and D.
Case 3,1: B is the common friend. Then we have edges AC, BC, AE, CE, AB, BD. This is a problem because A and C have two common friends (B and E), so this is not possible.
Case 3,2: C is the common friend. Then we have edges AC, BC, AE, CE, CD. This is fine.
Case 3,3: E is the common friend. Then we have edges AC, BC, AE, CE, DE. This is fine.

Next, consider A and E.
Case 1,2,1: B is the common friend. Then we have edges AB, AC, BC, CD, BE. This is fine.
Case 1,2,2: C is the common friend. Then we have edges AB, AC, BC, CD, CE. This is fine.
Case 1,2,3: D is the common friend. Then we have edges AB, AC, BC, CD, AD, DE. This is a problem because A and C have two common friends (B and D). This is not possible.
Case 1,3,1: B is the common friend. Then we have edges AB, AC, BC, AE, DE, BE. This is a problem because A and B have two common friends (C and E). This is not possible.
Case 1,3,2: C is the common friend. Then we have edges AB, AC, BC, AE, DE, CE. This is a problem because A and C have two common friends (B and E). This is not possible.
Case 1,3,3: D is the common friend. Then we have edges AB, AC, BC, AE, DE, CE. This is fine.
Case 2,1,1: B is the common friend. Then we have edges AB, AC, BC, BE, CD. This is fine.
Case 2,1,2: C is the common friend. Then we have edges AC, BC, CD, CE. This is fine.
Case 2,1,3: D is the common friend. Then we have edges AC, AD, BC, CD, DE. This is fine.
Case 3,2,1: C is the common friend already. We keep edges AC, BC, AE, CE, CD. This is fine.

At this point, we considered A and every other vertex. Now, we start with B,C. Then B,D. Then B,E. After that, we do C,D. Then C,E. Finally, D,E. In each case we need to find exactly one common friend. In the end, we wind up with every possible case detailed. This is a very tedious way of doing it, but I am not sure how else it would be possible to verify.

8. ## Re: Graph Theory Question Originally Posted by inayat How do you know 120 of them look like that?
I assume it will look like the image you have. Then there are five possible letters for the center vertex. We have to put 2 of the remaining 4 letters at the top (and the other two at the bottom). There are $\dbinom{4}{2}$ ways of doing that. Then, for the two letters at the top, we choose one of them to be on the left and one on the right. Then for the two letters at the bottom, we choose one of them to be on the left and one on the right. That is:

$$\dbinom{5}{1}\dbinom{4}{2}\dbinom{2}{1}\dbinom{2 }{1} = 5\cdot 6\cdot 2\cdot 2 = 120$$

But, I'm not sure about permuting the vertices on the top and bottom. Maybe there are only 30 possibilities.