Graph G and H are respectively connected and disconnected. What can we say…
Graph G and H are respectively connected and disconnected. What can we say about G’ and H’?
Answer: B. Can’t say about G’ but H’ is connected — Answer: Can’t say about G’ but H’ is connected. Explanation: Why the complement of the disconnected graph is connected: If a graph has two or more components,…
- A.
G’ is disconnected and H’ is connected
- B.
Can’t say about G’ but H’ is connected
- C.
G’ is disconnected but can’t say about H’
- D.
Can’t say about any of them
Attempted by 159 students.
Show answer & explanation
Correct answer: B
Answer: Can’t say about G’ but H’ is connected.
Explanation:
Why the complement of the disconnected graph is connected: If a graph has two or more components, then any vertex in one component is adjacent in the complement to every vertex in any other component. Thus for any two vertices either they are adjacent in the complement (if they came from different components originally) or they can be joined by a two-step path through a vertex in another component; hence the complement is connected.
Why we cannot decide the complement of the connected graph in general: There are examples both ways.
Example where the original graph is connected but its complement is disconnected: a complete graph on two or more vertices is connected, and its complement has no edges, so the complement is disconnected.
Example where the original graph is connected and its complement is also connected: a path on four vertices is connected, and its complement is connected.
Therefore the correct conclusion is: we cannot say whether the complement of the connected graph is connected or disconnected, but the complement of the disconnected graph is always connected.