556 views
3 votes
3 votes
  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.

3 Answers

0 votes
0 votes

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

0 votes
0 votes

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) 

0 votes
0 votes

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.

Related questions