DiscreteMth

G' is the complementary graph of G.
Let's assume G is not connected. We will prove that G' is connected.

Since G is not connected, there are two points A, B that has no path connecting them. So, in G', {A,B} in E'. We will show that every vertex in G' is edged with either A or B, and this will show that G' is connected.

Again without loss of generality, assume {v,A} not in E'. We will show that {v,B} in E'.

Since {v,A} not in E', {v,A} is in E. If {v,B} is not in E', this implies {v,B} in E, which means {A,v,B} is a path from A to B, a contradiction to our choice of A and B. Therefore {v,B} is in E'.

Assume both G and G' is not connected --------- (*)
There must exist some {u, v} disconnected in G
There must exist some {u', v'} disconnected in G'

By definition {u, v} must be in E' and {u', v'} be connected in E
Now we look at whether there is an edge between {u, u'}
Case 1)
{u, u'} in E, {v, u'} not in E
=> {v, v'} not in E, or otherwise {u, v} is connected in G by path u->u'->v'->v => {v, v'} in E'
=> {u', v'} is connected in G' by path u'-> v-> v'}, contradiction

Case2)
{u, u'} not in E, {v, u'} in E
=> {u, v'} not in E, or otherwise {u, v} is connected in G by path u->v'->u'->v
=> {u, v'} in E'
=> {u', v'} is connected in G' by path u'->u->v', contrdiction

Case 3)
{u, u'} in E, {v, u'} in E
=> Contradiction because {u,v} connected in E by path u->u'->v

Case 4)
{u, u'} not in E, {v, u'} not in E
=> u -> u' -> v is connected in G'
=> v' is cannot be connect to u nor v in G', otherwise will connected to u' in G'
=> v' is connected to u and v in G
=> u and v is connected in G, contradiction.

We have explored all possible cases but all leads to contradication.
Proof by contradiction, the assumption (*) must fail.