Prove that if G is a graph of order n 3 with the property t

Prove that if G is a graph of order n > 3 with the property that deg u + deg v > n for every pair u, v of nonadjacent vertices of G, then G nonseparahle.

Solution

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

For all couple of nodes (u,v) such that uH1,vH2, deg(u)+deg(v)n holds, because they\'re not adjacent.

So

rsnuH1,vH2[deg(u)+deg(v)]

=suH1deg(u)+rvH2deg(v)

sr(r1)+rs(s1)

=rs(r+s2)

This gives r+s+1=nr+s2 or 1-2 which is not possible

Therefore G is nonseparable.