# Draw a non-planar graph whose complement is a non-planar graph

I have been teaching myself graph theory. I am stuck at solving this problem on my own.

Please provide an example of such a graph.

What approach would you take to draw such a graph?

-
What about inserting one additional vertex on each edge of the complete bipartite graph $K_{3,3}$? – Martin Sleziak Jan 16 '13 at 13:15
If you know that $K_n$ is non-planar, attach another $n$ vertices (with no edges anywhere). Likewise, if you know that $G$ is non-planar, just attach $G'$ (and you can add edges between G and G' if you want, to make it a connected graph. – Calvin Lin Jan 16 '13 at 13:17
Add this an answer, I will accept it. I returned to doing graph theory again and now this idea appears so simple. To quote an example, I drew UG and added six more isolated vertices. Now, in G' K6 is a subgraph and therefore G' is nonplanar. – Sudheer May 21 '15 at 12:14

One way to think of non-planar graphs is graphs with too many edges. You can use Euler's polyhedron formula $V - E + F = 2$ to quantify this based on the vertices $V$, edges $E$, and faces $F$ of a graph, and you get that if a graph is planar then $E \leq 3V-6$.

Since a graph and its complement add to the complete graph with $\frac{n(n-1)}{2}$ edges, if you pick a non-planar graph with fewer than $\frac{n(n-1)}{2} - (3n-6)$ edges, the complement has too many edges and they are both non-planar.

So, for example, take a graph on $10$ vertices and connect $5$ of them into $K_5$, while leaving the others disconnected. In the complement, the disconnected vertices form another $K_5$, so they are both non-planar.

-
thanks for the edit! – Michael Biro Jan 16 '13 at 14:14
This answer is correct and easy to follow if you already know about Euler's formula. The text I am reading introduced the concept of planar and nonplanar graphs before Euler's formula. So, at that time, it was hard for me to follow your suggestion. – Sudheer Jun 2 '15 at 14:36

Non-planar graphs include (in a certain sense) either the complete graph $K_5$ or the complete bipartite graph $K_{33}$. To me the latter seems easier to work with. Now, if we just take $K_{33}$, it's complement is not non-planar. But if we take $K_{33}$ and add a second component consisting of three vertices, then when we take the complement this component will form a $K_{33}$ with each of the existing components, so the resulting graph will also be non-planar.

We can connect the three new vertices to each other however we want without affecting the result, and if we want a connected graph we can connect them to one of the existing parts of the $K_{33}$--in the complement graph they will still form a $K_{33}$ with the other component.

Here's an example of such a graph:

-

I drew UG and added six more isolated vertices. Now, in G' K6 is a subgraph and therefore G' is nonplanar.

-
I think I understand what you are doing. It wouldn't hurt to say what UG means, though ;-) – Jyrki Lahtonen Jul 27 '15 at 13:06
@NaN: This is simply an admittedly terse way of translating Calvin's comment to an answer. Therefore it IS an answer. – Jyrki Lahtonen Jul 27 '15 at 13:08
UG is the Utility Graph. See en.wikipedia.org/wiki/Complete_bipartite_graph#/media/… – Sudheer Jul 28 '15 at 12:24