Let G be a simple connected graph. Let in which V(G) is the set of vertices of G and d(u,v) is the distance between u and v. Let and . Now prove that if then there is a vertex v such that .

Printable View

- Oct 26th 2012, 04:46 AMxixigraph theory question
Let G be a simple connected graph. Let in which V(G) is the set of vertices of G and d(u,v) is the distance between u and v. Let and . Now prove that if then there is a vertex v such that .

- Oct 26th 2012, 12:23 PMjohnsomeoneRe: graph theory question

- Oct 26th 2012, 07:58 PMxixiRe: graph theory question
So we have for example, . But maybe for some there is no for which , now how can I prove that and then we have for every k between rad(G) and diam(G), k is for some ?

- Oct 26th 2012, 11:06 PMjohnsomeoneRe: 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.