Results 1 to 2 of 2

Thread: 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 $\displaystyle x \in V(G)$ satisfies $\displaystyle \delta (x) \geq \fraq{(v-1)/2}$.Show that G has diameter no greater than 2.

    Where $\displaystyle \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 $\displaystyle u$ and $\displaystyle w$, we have to prove that the distance between them is at most 2.

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

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

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

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

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

    Note that we didn't use the hypothesis that G was connected, but we needed $\displaystyle G$ to be a simple graph .
    Last edited by PaulRS; Sep 20th 2010 at 07: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: Mar 8th 2012, 06:07 AM
  2. Graph theory degree
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: Mar 8th 2012, 06:00 AM
  3. [SOLVED] Diameter 3 Graph and and minimum maximum degree
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Dec 22nd 2011, 02:57 AM
  4. Graph theory: Prove min degree(G_n) >= k
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 9th 2011, 08:26 PM
  5. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM

Search Tags


/mathhelpforum @mathhelpforum