1. ## graph theory question

Let G be a simple connected graph. Let $\displaystyle 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 $\displaystyle rad(G)=Min_{v \in V(G)} e(v)$ and $\displaystyle diam(G)= Max_{v \in V(G)} e(v)$. Now prove that if $\displaystyle rad(G) \le k \le diam(G)$ then there is a vertex v such that $\displaystyle e(v)=k$.

2. ## Re: graph theory question

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

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

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

$\displaystyle \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.$

$\displaystyle \text{What can you say about the values } e(v_1), e(v_2), ... , e(v_m) ?$

3. ## Re: graph theory question

So we have for example,$\displaystyle e(v_2) \in \{rad(G), rad(G)+1, rad(G)-1\}$. But maybe for some $\displaystyle k(rad(G)<k<diam(G))$ there is no $\displaystyle i(1<i< m)$ for which $\displaystyle e(v_i)=k$, now how can I prove that $\displaystyle e(v_i)=rad(G)+(i-1)$ and then we have for every k between rad(G) and diam(G), k is $\displaystyle e(v_i)$ for some $\displaystyle i(1 \le i \le m)$ ?

4. ## 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.