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.
Best Answer
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 $$