Guichard-Combinatorics-Graph-Theory · Problem 5.7.11

Graph Theory

Mathematics — Probability · connectivity

Problem

Show that the complement of a disconnected graph is connected. Is the complement of a connected graph always disconnected? (The complement

\overline{G}

of graph

G

has the same vertices as

G

, and

\{v, w\}

is an edge of

\overline{G}

if and only if it is not an edge of

G