Radius and Diameter (Graph Theory)?

Question

I'm trying to figure out this proof for my exam later today and my professor and the assigned book are of little help... Any help from anyone out there would be great! Thanks in advance!

Prove that

rad <= diam <= 2*rad

(radius is less than or equal to diameter which is less than or equal to 2 times the radius)

Answer 1

Guys, this is graph theory, not a circle.

I hadn't heard of a radius in a graph before, that's quite interesting. Anyway, definitions are here for reference:
http://en.wikipedia.org/wiki/Distance_(graph_theory)

Certainly, straight from the definition we know that r <= d, since d is the maximum of a set and r is the minimum of the same set.

So what we really need to prove is d <= 2r. If you think about this one for a bit, it's a bit like the triangle inequality in a way. I think I'll do this by contradiction. Let G be a graph with radius r and diameter d, and suppose d>2r. Consider the pair of vertices u, v in G with the distance between them being d (they are peripheral vertices). Then consider a vertex w with minimum eccentrictiy that is in the same component of G as u and v (I'm not sure if you would need to prove that this exists or not; the statement may even fail for disconnected graphs, so I'm assuming G is connected; you can probably toss in a small bit to take care of the case when G is disconnected).

Okay, so we've got u and v which are distance d apart, and since w has minimum eccentricity, the distance from u to w and from v to w is <=r. But the path from u to w to v has length <=2r in this case, so that u and v must have eccentricity less than or equal to this, which contradicts our eccentricity of d (>2r).

I'll check back in a bit, and I'll see if I can get something for the disconnected case.

EDIT: I've fixed up the proof a tiny bit, and I think contradiction isn't necessary. You could probably rewrite as a direct proof and it would be more elegant, but you'll use the same ideas.

As for the disconnected case: I think the definitions for eccentricity might fail here. If there is no path from u to v, then the eccentricity of u might be defined as infinity. So for a disconnected graph, eccentricity is infinite for all vertices, and comparisons kind of fall apart. That's pretty simple, I'm surprised I didn't think of it before.

Answer 2

Graph Theory Diameter

Answer 3

rad < dia = 2 * rad

Answer 4

Um...these are defined terms.

Regardless, D = 2R. D is never < 2R

Answer 5

2 pi r

thats all I know...for a form 2 student...>.<