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.


This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .