One of my workshop questions in preparation for my exams is:
For any non-adjacent nodes $x,y$ on a simple graph G on $n$ vertices. We have $\deg(x) + \deg(y) \geq n-1$ Prove that G is connected.
Now I understand what the question is asking however during trying to think about how it works, I found that in a connected graph: take graph 9 From the picture below, if the bottom $2$ nodes are $x$ and $y$, but we made it a 5 node disconnected graph. Then we have $\deg(x) + \deg(y) = 2 + 2 = 4 = 5-1 = 4$ so the equation holds, but the graph is disconnected. I'm unsure what I am missing. Any help would be appreciated thank you.
This is an answer given by logarithm in comments:
Prove the contrapositive. Assume that A,B are two different connected components of G. Take $x\in A$ and $y\in B$. Then the degree of x is not more than |A|-1 and the degree of y is not more than $|B|-1$. Therefore, $$\deg(x)+\deg(y)\leq |A|-1+|B|-1=|A\cup B|-2\leq|G|-2,$$ where the equation $|A|+|B|=|A\cup B|$ follows due to A and B being disjoint.