Guichard-Combinatorics-Graph-Theory · Problem 5.1.1

Graph Theory

Mathematics — Probability · graph-theory-basics

Problem

The complement

\overline{G}

of the simple graph

G

is a simple graph with 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

. A graph

G

is self-complementary if

G \cong \overline{G}

. Show that if

G

is self-complementary then it has

4k

4k + 1

vertices for some

k

. Find self-complementary graphs on 4 and 5 vertices.