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.


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.


$$ 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 $$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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