Graph complement

Let \(G\) be an undirected graph without self-loops and multi-edges. The complement of graph \(G\) is a graph \(\overline{G}\) on the same vertices such that two vertices of \(\overline{G}\) are adjacent (i.e., connected by an edge) if and only if they are NOT adjacent in \(G\). A graph is said to be connected if there is a path from any vertex to any other vertex in the graph.

  • Give an example of a graph \(G\) such that both \(G\) and \(\overline{G}\) are connected.

  • For any graph \(G\), prove that either \(G\) is connected or \(\overline{G}\) is connected.

Source: folklore

Related Content