Subscribe to the weekly news from TrueShelf

## 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

0

0

0

0

0

0

0

0

0

0