CMI2011-A-07

Question

Let $G=(V, E)$ be a graph. Define $\overline{G}$ to be $(V, \overline{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \overline{E}$ if and only if $(u, v) \notin E$. Then which of the following is true?

• A. $\overline{G}$ is always connected.
• B. $\overline{G}$ is connected if $G$ is not connected.
• C. At least one of $G$ and $\overline{G}$ connected.
• D. $G$ is not connected or $\overline{G}$ is not connected

Answer 1

A correct answer would be (C) At least one of G and G-bar is connected.

Option (A): It is straight forward wrong.

Option (B): This is a subset of Option (C).

Option (D): This also implies that G and G-bar are not connected at the same time, which is impossible. 

Here are the total possibilities:

$$\begin{array}{|l|l|l|} \hline \textbf{G} & \overline{\boldsymbol{G}} & \textbf{Possible/Not Possible}\\\hline \text{Connected} & \text{Connected}& \text{Possible}\\\hline \text{Connected} & \text{Disconnected}& \text{Possible}\\\hline \text{Disconnected} & \text{Connected}& \text{Possible}\\\hline \text{Disconnected} & \text{Disconnected}& \text{Not-Possible} \\\hline \end{array}$$                                                                 

Comments

I think that If G is disconnected ,then G' is disconnected is correct .

If we consider cycle graph C4 , then G may be :   1---------2

                                                                                   3---------4

Then G' is :     1         2

                       3          4   ( Vertical line from 1-----3  and 2-----4)

Please clear my doubt

---

@sutanay3-No. To prove a claim, it must hold under all circumstances.

Consider G to be a null graph on 5 vertices.$G'$ will be a complete graph on 5 vertices.

---

Yes I was also thinking that in general, if we take any graph, then if G is disconnected, then G ' canntbe disconnected. But that example strike my mind.

In the best answer it is written as impossible but I have given one example for it.

@Ayush Upadhyaya  Sir

Here , the null graph is also connected. There G' which is a complete graph is also connected.

Answer 2

Option A - False. Counter Example - Complete Graph

Option B- $\overline{G}$ is connected if G is not connected. True

Proof -  Let G is disconnected. Suppose u and v are vertices. If (u.v) is not an edge in G, then it is an edge in $\overline{G}$, and so we have a path from u to v in $\overline{G}$. On the other hand, if (u,v) is an edge in G, then this means u and v are in the same component of G. Since G is disconnected, we can find a vertex w in a different component so that neither (u,w) nor (v,w) is edges of G. Then (u,w) and (v,w) are edges of $\overline{G}$ and hence there exist a path from u to v in $\overline{G}$.

This shows that any two vertices in $\overline{G}$ have a path (in fact a path of length one or two) between them in $\overline{G}$, so $\overline{G}$ is connected.

Option C - At least one of G and $\overline{G}$ connected.

Which means $\overline{G}$  is connected if G is not connected and vice versa. 

Proof:

If  $\overline{G}$ is not connected, then there exists two disjoint sets V1 and V2 such that V1 $\subset V$ and V2 $\subset V$ and for all v1∈V1 v2∈V2 we have (v1,v2) ∉ $\overline{E}$ .This means that $ \forall v1 \in V1 \ and \ v2 \in V2$ we have $(v1,v2)∈E$ Hence G is connected.

Option D - G is not connected or $\overline{G}$ is not connected. 
False. Both can be connected at the same time. 

Option B is a subset of option C.

So Option C is correct. At least one of G and $\overline{G}$ connected.

Comments

@Soumya29 we always go for stricter one right?

---

@tusharp Yes. 

---

option b implies option c as c covers b we go for c.

I am not able to prove C -> B as false. :(

I think it is B <=> C.

---

@tusharp
Suppose A = G is connected
B = $\bar G$ is connected
Option C - $A' \implies B \ OR\   A \vee  B$
Option D - $  A \vee  B$
Yes, you are right.. Both statements are logically equivalent. :)

Answer 3

A) If G is a complete graph then G' is a null graph which eliminates option A) 

D) Both G and G' can be connected. Example :

: 

B) Suppose C1,C2,C3,...Cm be connected components in graph G (Note that these m components though are connected, there willnot be any edge between any 2 components). Now in G', all vertices of a component (say C1) will be connected to all vertices of all other components (C2,C3,C4,...). Similiarly, all vertices of a component (say C2) will be connected to all vertices of all other components (say C1,C3,C4,...).. Now G' is connected because 

                  1) Any vertex of a component Ci is connected to all other component's vertices. So there is a connection between all components.

                  2) Any 2 vertices say v1 and v2 inside a component (say C1) will also be connected because there is an edge from v1 of C1 to any vertex of C2 and there is an edge from that vertex of C2 to v2. 

C) If B) is true C) should also be TRUE... Hence both B) and C) are correct.

Answer 4

Option B is the subset of option C. Hence option C is the correct answer.