JEST2020

Question

1. Let G(V,E) be a simple graph. Let G’(V,E’) be a graph obtained from G such that (u,v) is an edge in G’ if (u,v) is not an edge in G. Which of the following is true?

 

 

1. At least one of G or G’ are connected.
2. G is necessarily disconnected.
3. Both G and G’ are disconnected.
4. None of the above.

Answer 1

I think the Answer is (A). I tried to draw few example graph and checked it out. But open to suggentions and corrections

Answer 2

Since (u,v) is an edge in G’ and (u,v) is not an edge in G it is possible that the G’ be the complement of the G then according the property a connected graph complement can be connected or disconnected so I think it is (A) 

Answer 3

Option A  will be true and necessarily true always. Here graph G’  is complement of graph G. So even if G is completeyly disconnected, G’ has to be connected of vice versa.