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.


1 Answer 1


Suppose that $G$ is not connected. Consider the smallest connected component of $G$.

You take it from here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.