Results 1 to 4 of 4

Math Help - graph theory question

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    59
    Thanks
    3

    Question graph theory question

    Let G be a simple connected graph. Let e(v)=Max_{u \in V(G)} d(u,v) in which V(G) is the set of vertices of G and d(u,v) is the distance between u and v. Let rad(G)=Min_{v \in V(G)} e(v) and diam(G)= Max_{v \in V(G)} e(v). Now prove that if rad(G) \le k \le diam(G) then there is a vertex v such that e(v)=k.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: graph theory question

    \text{Show: If } w \text{ and } v \text{ are adjacent, then } |e(w) - e(v)| \le 1.

    \text{(That's shorthand for } (e(w) - e(v)) \in \{ -1, 0, 1 \}, \text{ meaning e increases or decreases by at most 1.)}

    \text{Choose } u_0, u_1 \in V(G) \text{ such that } e(u_0) = \text{rad}(G), e(u_1) = \text{diam}(G).

    \text{Since } G \text{ is connected, there's a path } v_1 = u_0, v_2, ... ,  v_m = u_1 \text{ from } u_0 \text{ to } u_1.

    \text{What can you say about the values } e(v_1), e(v_2), ... , e(v_m) ?
    Last edited by johnsomeone; October 26th 2012 at 01:34 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2010
    Posts
    59
    Thanks
    3

    Re: graph theory question

    So we have for example, e(v_2) \in \{rad(G), rad(G)+1, rad(G)-1\} . But maybe for some k(rad(G)<k<diam(G)) there is no  i(1<i< m) for which e(v_i)=k, now how can I prove that e(v_i)=rad(G)+(i-1) and then we have for every k between rad(G) and diam(G), k is e(v_i) for some i(1 \le i \le m) ?
    Last edited by xixi; October 26th 2012 at 09:14 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: graph theory question

    This is one of those things that can of course be proven, but a proof will make it seem more complicated than the obvious reason why it's true.

    You step along a path, and at each disceret step, e changes by -1, 0, or 1. You start stepping where e = rad(G). You end stepping where e = diam(G) > rad(G). You must necessarily step through every integer between them.

    You could prove that by induction on the length of the path, or by contradiction with the smallest value "skipped", or by an algebraic representation of the change at each step, or other ways I'm sure.

    Ex: Suppose you start with $5. You have finite number (say 8) of financial transactions. At the conclusion of each transaction, you've either gained $1, lost $1, or experienced no change. When you're done with all the transactions, you end up having $9. Necessarily, at the conclusion of at least one of those transactions, you had $6. Likewise for $7, and for $8.
    Last edited by johnsomeone; October 27th 2012 at 12:14 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Question 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 24th 2012, 12:51 AM
  2. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 13th 2010, 03:32 PM
  3. Two Graph theory question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 8th 2009, 07:18 PM
  4. Graph theory question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 26th 2007, 08:10 AM
  5. Graph Theory Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 26th 2007, 07:21 AM

Search Tags


/mathhelpforum @mathhelpforum