Introduction to Graph Theory · Problem 2.13

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · complement-graph-path-length

Problem

Let

G = (V, E)

be a simple graph. The complement graph

\overline{G}

G

is defined to be the simple graph

(V, \mathcal{P}_2(V) \setminus E)

. (Thus, two distinct vertices

u

and

v

V

are adjacent in

\overline{G}

if and only if they are not adjacent in

G

.) Prove that at least one of the following two statements holds: • Statement 1: For each

u \in V

and

v \in V

, there exists a path from

u

v

G

of length

\leq 3

. • Statement 2: For each

u \in V

and

v \in V

, there exists a path from

u

v

\overline{G}

of length

\leq 2