Question

Show that if \({\bf{G}}\) is a simple graph with at least 11 vertices, then either \({\bf{G}}\)or\({\bf{\bar G}}\), the complement of \({\bf{G}}\), is non-planar.

Short answer

The complement of\(G\), is non-planar.

Step-by-step solution

Introduction

A graph is said to be non planar if it cannot be drawn in a plane so that no edge cross.

Step 2: Prove that if G is a simple graph with at least 11

Suppose that\(G\)is planar then:

Number of edges is

\(e \le 3v - 6\)at\(v = 11,\;e = 27\)

(In case\(G\)is not connected it must have fewer edges)

In the same way\(\bar G\)has most\(27\)edges.

But,\(\bar GUG\)is written as\({K_{11}}\).

\({e_{{K_{11}}}} = 55\)

\(55 > 27 + 27\)

Hence, the complement of\(G\), is non-planar.