Combinatorics and Graph Theory · Problem 5.7.11

Graph Theory — David Guichard

Mathematics — Combinatorics · 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