Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
2  
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 comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
    
thanks for the edit! –  Michael Biro Jan 16 '13 at 14:14
add comment

Your Answer

 
discard

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.