Prove that if $deg(u)+deg(v)\geq n$ for every pair $u.v$ of non adjacent vertices of $G$, then $G$ is non-separable.

Question

Prove that if $G$ is a graph of order $n \geq 3$ with property that $deg(u)+deg(v)\geq n$ for every pair $u.v$ of non adjacent vertices of $G$, then $G$ is non-separable.

I'm trying to show that $G$ has no cut-vertex, but I can't see how the property $deg(u)+deg(v)\geq n$ can help me. I would appreciate any hint.

Answer 1

Suppose that $G$ is separable, and let $a$ be the cut node, $H_1$ and $H_2$ the nodes in the two distinct parts of the graph, so that $|H_1|+|H_2|+1=r+s+1=n$.

For all couple of nodes $(u,v)$ such that $u\in H_1$, $v\in H_2$, $deg(u)+deg(v)\geq n$ holds, because they're not adjacent.

So

$$ rsn\le \sum_{u\in H_1, v\in H_2}[deg(u)+deg(v)]=\\=s\sum_{u\in H_1}deg(u)+r\sum_{v\in H_2}deg(v)\le sr(r-1)+rs(s-1)=rs(r+s-2) $$

And this is absurd

$$ r+s+1=n\le r+s-2 $$

Answer 2

Simpler proof can be:

If we assume our graph to have $\mathrm{deg}(u)+\mathrm{deg}(v) \ge n$ for every pair of non adjacent vertices $u$ and $v$, our graph is therefore Hamiltonian.

And by definition, a Hamiltonian graph can not have a cut vertex, therefore making it nonseparable.