Results 1 to 5 of 5

Math Help - Diameter 3 Graph and and minimum maximum degree

  1. #1
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Diameter 3 Graph and and minimum maximum degree

    Problem:
    Let G be a graph on n >= 4 vertices such that for any two vertices, v_1 and v_2, there is a path of length <= length 3 with endpoints of v_1 and v_2. Prove that G has a point of degree >= n^(1/3).

    My attempt:
    I would like to prove the result by contradiction. Assume that all vertices have degree strictly less than n^(1/3). Then the sum of degrees is less than n(n^(4/3)) and the number of edges is strictly less than (1/2)n^(4/3). I would like to prove that then there are not enough edges to connect all vertices in the manner described, but don't know where to turn to figure out what the minimum number of edges needed would be.

    Any suggestions would be appreciated. Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Diameter 3 Graph and and minimum maximum degree

    Quote Originally Posted by jsndacruz View Post
    I would like to prove the result by contradiction. Assume that all vertices have degree strictly less than n^(1/3). Then the sum of degrees is less than n(n^(4/3))
    Maybe n^(4/3)?

    You could try using the inequality related to Moore graphs.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2011
    Posts
    45

    Re: Diameter 3 Graph and and minimum maximum degree

    Wow, I've never heard of that before. Thanks! I have to study for linear now, but I'll tackle this problem again tomorrow night.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: Diameter 3 Graph and and minimum maximum degree

    Please share solution if u can
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Diameter 3 Graph and and minimum maximum degree

    Assuming the contrary, the maximum degree is < n^{1/3}. Then, using the equality from the link above, we get that n < 1+n^{1/3}(1+n^{1/3}-1+n^{2/3}-2n^{1/3}+1). Solving this gives n < 4.2, i.e., n <= 4. By assumption, n >= 4, so we get a contradiction except in the case n = 4. You must show manually that when n = 4, the maximum degree cannot be <n^{1/3}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: August 21st 2011, 01:12 PM
  2. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  3. Graph theory proof-diameter/degree relationship
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: September 20th 2010, 05:41 AM
  4. Maximum and minimum of a graph
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: September 25th 2009, 12:47 PM
  5. Maximum and Minimum of a Graph
    Posted in the Calculus Forum
    Replies: 0
    Last Post: September 23rd 2008, 07:21 PM

/mathhelpforum @mathhelpforum