Results 1 to 8 of 8

Thread: Graph Theory Question

  1. #1
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    Question Graph Theory Question

    Graph Theory Question-sld.png

    How can this be justified fully?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,865
    Thanks
    3074

    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    Re: Graph Theory Question

    Quote Originally Posted by HallsofIvy View Post
    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:

    Graph Theory Question-skm.png
    Graph Theory Question-skm-2.png

    Is this right?

    Here's the graph
    Graph Theory Question-skm-3.png
    Last edited by inayat; Apr 5th 2018 at 05:33 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,571
    Thanks
    1437

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    Re: Graph Theory Question

    Quote Originally Posted by SlipEternal View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    Re: Graph Theory Question

    Quote Originally Posted by SlipEternal View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,571
    Thanks
    1437

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,571
    Thanks
    1437

    Re: Graph Theory Question

    Quote Originally Posted by inayat View Post
    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.
    Last edited by SlipEternal; Apr 6th 2018 at 08:29 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 14th 2011, 12:15 AM
  2. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 13th 2010, 02:32 PM
  3. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 29th 2007, 02:28 AM
  4. Graph Theory Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 26th 2007, 06:21 AM

/mathhelpforum @mathhelpforum