Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected.
Decide whether the above claim is true or false, and give a proof of either the claim or a counter example.
I drew out a few examples and the claim seems to hold, and I cannot find a counter example to prove it is false, which leads me to believe the claim is true. However, I am having a really hard time generating a proper proof.