# Graph Theory proving planarity

I have these set's of graphs:

I used Euler's inequality, and the 4 color theorem which resulted in a inconclusive result. Using Kuratowski's theorem I was unable to create a K3 3 or K5 graph. So does this prove that the graphs are planar? How do we really know that there does not exist a K3 3 or K5? I did use planar embedding and was able to put it in a form where the edges do not overlap, but the method does not seem rigorous enough to prove planarity.

• The 4-colour theorem can only tell you that a graph is non-planar if you can prove that it has no proper 4-colouring, which is likely to be quite difficult. (For example, it's not true that all 4-colourable graphs are planar, since there are non-planar bipartite graphs, such as $K_{3,3}$.) – David Richerby Mar 16 '17 at 14:12
• The Kuratowski / Wagner / Robertson-Seymour theorems are about forbidden minor graphs. For an embedding of a graph onto a surface with an Euler characteristic of 2 (i.e. a 2D plane) you can demonstrate planarity by creating a planar embedding and non-planarity by finding either $K_{3,3}$ or $K_5$ forbidden minor graphs. For graph $G$ you can delete vertex $f$ and edge $cg$ and you have a $K_5$ minor graph which demonstrates non-planarity. For graph $H$ you can move $b$ inside the polygon $acgfe$ and $d$ inside the polygon $aefg$ and you have a planar embedding. – MT0 Mar 16 '17 at 15:23

Graph $G$ is not planar. The subgraph you get by deleting the edges $ab,$ $ad,$ $bd,$ $cg,$ $eg$ is homeomorphic to $K_{3,3};$ the vertices $a,b,d$ are connected to the vertices $e,f,g$ by the internally disjoint paths $ace,$ $af,$ $ag,$ $be,$ $bf,$ $bg,$ $de,$ $df,$ $dg.$

Graph $H$ is planar. Plot $a$ at $(0,0),$ $b$ at $(2,0),$ $c$ at $(1,1),$ $d$ at $(1,3),$ $e$ at $(1,4),$ $f$ at $(2,3),$ $g$ at $(1,2),$ and draw all the edges as straight line segments.

Here's an illustration of a subgraph of $G$ which is a subdivision of $K_5$, so Kuratowski's Theorem implies $G$ is non-planar:

Here's a planar drawing of $H$, demonstrating that it's planar:

If it contained a subgraph which is a subdivision of $K_5$ or $K_{3,3}$, this planar drawing would not be possible.

• Nice pictures!.. – Matthew Leingang Mar 16 '17 at 15:52

Both of these graphs have spanning cycles. There is an algorithmic way to check if a graph with a spanning cycle is planar using the concept of a "conflict graph".

Pick a spanning cycle, and draw the graph with that spanning cycle as a circle, and all the edges off the spanning cycle as chords of that circle. For the first graph, I chose the cycle a, b, f, d, e, g, c. My graph drawing software (Sage) is awkward with vertex labels, and so here I've named them respectively 1, 2, 3, and so on.

The conflict graph is a new graph in which the vertices are the chords of this drawing of your graph. Two chords are considered to "conflict", and are thus adjacent in the conflict graph, if and only if they cross in the above drawing. The idea is this. Let G be your graph and C the spanning cycle. Any planar embedding of G must represent C as some sort of a closed curve - not necessarily a circle, but some closed curve which will divide the plane into an inside and an outside. If two chords conflict, then they necessarily have to be drawn on different sies of this curve (one outside and one inside) in order not to cross.

The conflict graph here looks like this:

The theorem is: a graph with a spanning cycle is planar if and only if its conflict graph is bipartite. This is obvious given what we said above: we need a 2-coloring for the conflict graph using the colors "inside" and "outside". If the conflict graph is non-bipartite, two chords will necessarily have to be drawn on the same side of the cycle. In this case, the conflict graph is obviously non-bipartite since it has an obvious odd cycle.

You can read more about conflict graphs in Douglas West's book, Introduction to Graph Theory.

• An answer where I learned a new generally useful principle? Excellent, +1. – Wildcard Mar 16 '17 at 23:09

In the first graph, there is a subdivision or minor of $K_5$ formed by $a$, $\{b,c\}$, $d$, $\{e,f\}$, $g$. Therefore it is not planar.

The second graph has a planar embedding. This is the definition of a graph being planar, so I have no idea what you mean by whether it is not rigorous.