Hi everyone. I've been thinking about this problem all weekend and I can't quite figure out how to do it. I know which theorems I need and understand them, but I just can't figure out how to put everything together in a proof.
Here's the problem:
(Note that Δ(G) = the vertex with maximum degree and δ(G) = the vertex with minimum degree)
Prove that if G is a graph of order n such that Δ(G) + δ (G) ≥ n - 1, then G is connected and diam(G) ≤ 4. Show that the bound n - 1 is sharp.
Now I know that the proof is going to involve this theorem in my text, but I just can't figure out how to use it.
Theorem: Let G be a graph of order n. If deg(u) + deg(v) ≥ n - 1 for every two nonadjacent vertices u and v of G, then G is connected and diam(G) ≤ 2.
There's also this: If G is a graph of order n with δ (G) ≥ (n - 1)/2, then G is connected.
Thanks!