Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: graph

  1. #1
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    graph

    graph-graph.png
    The first answer is G1 is 6? As the maximum distance between any two vertices ?
    and the second G2 is 10? for the same reason am i correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,837
    Thanks
    1089

    Re: graph

    I get 2 and 4 respectively. How did you get 6 and 10? Can you give an example of two vertices that are six apart in G1 or 10 apart in G2? The diameter is the longest shortest path. In G1, the distance from vertices 1 to 2 is 1. You could go 1-5-4-9-6-8-10-7-2 (a path of length 8), but that is not the distance between vertices 1 and 2. The distance is the length of the shortest path, which is 1. The diameter of the graph is the largest distance, given all distances between every two vertices.

    Let's look at distances from vertex 1:
    1-2 = 1
    1-2-3 = 2
    1-5-4 = 2
    1-5 = 1
    1-6 = 1
    1-2-7 = 2
    1-6-8 = 2
    1-6-9 = 2
    1-5-10 = 2
    By symmetry, this is the same as the distances for paths starting at 2, 3, 4, and 5. It is also the same for paths starting from the inner vertices to the outer vertices. We still need to check from the inner vertices to each other:
    6-9-7 = 2
    6-8 = 1
    6-9 = 1
    6-8-10 = 2
    By symmetry, this is the same as the distance from any inner vertex to any other inner vertex. So, the maximum distance between any two vertices will be 2.

    For G2, it is a little more difficult. From 1 to 11, the maximum distance that I could find was 4. I do not see any two vertices that would have a longer distance between them. There are not as many symmetries in this graph, so to brute force it, you would need to check the distance between every two vertices. Since there are 11 vertices, there are only $\dbinom{11}{2}=55$ different pairs to check distances. I believe you will find the answer to be 4, but I have not gone through them all.
    Last edited by SlipEternal; Aug 2nd 2017 at 05:41 AM.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    Re: graph

    Thanks SlipEternal ,with G1 I wasn't using paths directly and just making my own straight lines from the different vertices as the maximum distance between two vertices and interpreted the meaning of how to do them completely wrong
    for example I would go 1-3 =1 2-4 =1 3-5=1
    1-4 =1 2-5 =1 3-1= 1 in total adding to 6.
    I worked in a clockwise direction until I reached vertice 1 again .
    When our lecturer put the one example on the board it kind of looked like he did it this way and I think I was confused .
    Similar case for G2 ...Oh dear I will definitely need some practice with these .
    Your explanation is very good and I can make sense of it all .They tend to go very very quickly in the lectures and then we move on to another topic ..
    Thanks again SlipEternal and very much appreciated .
    Cheers
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Jan 10th 2015, 04:07 PM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2011, 09:59 AM
  3. Replies: 7
    Last Post: Aug 5th 2011, 01:30 PM
  4. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM
  5. Replies: 1
    Last Post: Feb 15th 2009, 05:35 AM

/mathhelpforum @mathhelpforum