Results 1 to 2 of 2

Math Help - Graph theory proof-diameter/degree relationship

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    7

    Graph theory proof-diameter/degree relationship

    Hi, all!
    Here's the problem I've been working on.

    Suppose G is connected and suppose every x \in V(G) satisfies \delta (x) \geq \fraq{(v-1)/2}.Show that G has diameter no greater than 2.

    Where  \delta (x) is the degree of a vertex.
    So, it shouldn't be hard, but I can't seem to get what the relationship between the degree of a vertex of a graph and its diameter is.
    Any help would be greatly appreciated!
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Pick a pair of vertices u and w, we have to prove that the distance between them is at most 2.

    If u and w were adjacent, we are done, their distance is not greater than 2.

    We consider now the case in which u and w are not adjacent.

    Suppose the statement were false, that is, each of the neighbours of u is not a neighbour of w.

    Since \delta (w) \geq {\frac{v-1}{2}} we have \delta(u) \leq v - 2 - \delta(w) \leq  v - 2 - \frac{v-1}{2} < {\frac{v-1}{2}} a contradiction since \delta(u)\geq {\frac{v-1}{2}} !

    The -2 comes from the fact that u can't be a neighbour of itself or w.

    Note that we didn't use the hypothesis that G was connected, but we needed G to be a simple graph .
    Last edited by PaulRS; September 20th 2010 at 08:42 AM. Reason: Had used v as the name of a vertex.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, Degree
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: March 8th 2012, 07:07 AM
  2. Graph theory degree
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: March 8th 2012, 07:00 AM
  3. [SOLVED] Diameter 3 Graph and and minimum maximum degree
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2011, 03:57 AM
  4. Graph theory: Prove min degree(G_n) >= k
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2011, 09:26 PM
  5. Replies: 0
    Last Post: September 25th 2010, 06:59 AM

Search Tags


/mathhelpforum @mathhelpforum