graph theory question

• Oct 26th 2012, 05:46 AM
xixi
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$.
• Oct 26th 2012, 01:23 PM
johnsomeone
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) ?$
• Oct 26th 2012, 08:58 PM
xixi
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) there is no $i(1 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)$ ?
• Oct 27th 2012, 12:06 AM
johnsomeone
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.