Results 1 to 7 of 7

Math Help - Graphs, Diameter related question.

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    4

    Graphs, Diameter related question.

    I have been trying to solve this question for a while now and the deadline is almost over so I have no option but to seek help.

    We have an undirected graph of n edges and we know that the degree of each edge is <\sqrt{n-1} the object is to prove that the diameter is \geq3. How can I do that?

    EDIT:
    we have n vertexes and the degree of each vertex is <\sqrt{n-1}
    Last edited by ogeraisi; January 11th 2011 at 10:59 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    [Edit: Do you really mean degree of each edge? or vertex? I am proceeding on the assumption that its the degree of a vertex]

    The diameter is the longest distance from any vertex to another vertex.

    Start at any vertex. The maximum number of other vertices reachable in one step is \sqrt{n-1}.
    Maximum reachable in 2 steps is \sqrt{n-1}(\sqrt{n-1} - 1).
    Argue that you cannot reach all vertices in 3 steps (so diameter greater than 3.
    Last edited by snowtea; January 11th 2011 at 10:19 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    4
    Quote Originally Posted by snowtea View Post
    The diameter is the longest distance from any vertex to another vertex.

    Start at any vertex. The maximum number of other vertices reachable in one step is \sqrt{n-1}.
    Maximum reachable in 2 steps is \sqrt{n-1}(\sqrt{n-1} - 1).
    Argue that you cannot reach all vertices in 3 steps (so diameter greater than 3.
    Thank you for your reply, I am not sure I understand the process
    lets say I take a graph of with n=6 if I choose one of the vertexes and go from there I would be able to reach 2<\sqrt{5} other vertex therefore in one step I have covered 3 of the 6 vertexes in the graph then in the second step from each of the new vertexes I've reached I would try to get their degree to 2<\sqrt{5} but each of them already has 1 so I will be drawing 1<\sqrt{5}-1 from each, in reality I would have already covered 5 out of the 6 vertexes while in calculations I would have 2=2*1<\sqrt{5}(\sqrt{5}-1) or if I keep the actual values \sqrt{5}(\sqrt{5}-1)=2.76393202 what am I missing?

    EDIT:
    Sorry I have misunderstood the suggested solution though I still am unable to comprehend it properly.
    Starting at any vertex the maximum number of other vertices reachable in one step is <\sqrt{n-1} and not \sqrt{n-1}.
    Maximum reachable in 2 steps is <\sqrt{n-1}(\sqrt{n-1}-1) in my previous example over n=6 vertexes we would have 2<\sqrt{5}(\sqrt{5}-1)=2.76 vertices when we would actually have 4 on graph
    Last edited by ogeraisi; January 11th 2011 at 10:53 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Alright, think of it like this.

    Start at a vertex v. Using the technique above, show that there is at least one vertex w which cannot be reached by v in 2 steps (just one is enough).

    So we know that there exists v and w such that their distance is at least 3. This means all the neighbors of v and w are different.

    Now draw all the neighbors of v and all the neighbors of w. Argue by the maximum degree, either v and w have distance > 3, or some pair of neighbors have distance > 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2011
    Posts
    4
    Quote Originally Posted by snowtea View Post
    Alright, think of it like this.

    Start at a vertex v. Using the technique above, show that there is at least one vertex w which cannot be reached by v in 2 steps (just one is enough).

    So we know that there exists v and w such that their distance is at least 3. This means all the neighbors of v and w are different.

    Now draw all the neighbors of v and all the neighbors of w. Argue by the maximum degree, either v and w have distance > 3, or some pair of neighbors have distance > 3.
    Thanks again for your help
    I think I understand the solution this time
    basically starting from vertex x and drawing \sqrt{n-1} vertices then starting from the new vertexes we arrived to we draw \sqrt{n-1}(\sqrt{n-1}-1) vertices from each so we got so far up to (the starting vertex) 1+\sqrt{n-1}+\sqrt{n-1}(\sqrt{n-1}-1}) which is equal to n however we know that the degree is actually <\sqrt{n-1} in each vertex so we would have covered <n vertexes in 2 steps which will cause us to go at least one more step to cover all of the remaining vertexes making the diameter length >2 which is equal to \geq3.

    That is what I understood so far as for the last line for drawing all of the neighbors of v and all of the neighbors of w well I did try drawing them over n=13 and the diameter was actually 3 and not more, isn't the explenation above a full solution?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Yes, you are correct.

    I misread the problem as diameter strictly greater than 3. However, with greater than or equal to 3, you have the full proof.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2011
    Posts
    4
    Quote Originally Posted by snowtea View Post
    Yes, you are correct.

    I misread the problem as diameter strictly greater than 3. However, with greater than or equal to 3, you have the full proof.
    great! thank you very much for your time and effort, much appreciated
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Diameter question.
    Posted in the Geometry Forum
    Replies: 4
    Last Post: June 2nd 2010, 09:35 AM
  2. Graphs and also Help with Question
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 24th 2009, 04:49 PM
  3. Question on planar graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 8th 2009, 11:35 AM
  4. graphs question 2
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: January 24th 2009, 06:20 PM
  5. Replies: 4
    Last Post: May 29th 2008, 03:53 AM

Search Tags


/mathhelpforum @mathhelpforum