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 ordernsuch that Δ(G) + δ (G) ≥n- 1, then G is connected and diam(G) ≤ 4. Show that the boundn- 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 ordern. 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 ordernwith δ (G) ≥(n- 1)/2, then G is connected.

Thanks!