Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
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:

enter image description here

share|cite|improve this answer
up vote 1 down vote accepted

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

share|cite|improve this answer
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… – Sudheer Jul 28 '15 at 12:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.