# Prove that the lattice graph of $D_{16}$ is not planar

How do we prove that the lattice graph of $D_{16}$ is non-planar?

I wanted to prove it using Kuratwoski's Theorem but was unable to do it. And to add one more question, are there any interesting implication of planarity in group theory?

• Can we find a sub-graph isomorphic to $K_5$ or $K_{3,3}$? – Grobber Dec 3 '13 at 23:43

## 2 Answers

Consider the subgraph with the following as vertices and edges.

$\langle sr,r^2 \rangle------D_{16} ------ \langle s,r^2 \rangle$

$\langle sr,r^2 \rangle------ \langle r^2 \rangle ------ \langle r^4 \rangle$

$\langle sr,r^2 \rangle------ \langle sr^3,r^4 \rangle------\langle sr^3 \rangle ------ \langle 1 \rangle$

$\langle sr^2,r^4 \rangle ------ \langle s,r^2 \rangle$

$\langle sr^2,r^4 \rangle ------ \langle r^4 \rangle$

$\langle sr^2,r^4 \rangle ------\langle sr^2\rangle------ \langle 1 \rangle$

$\langle s,r^4 \rangle ------ \langle s,r^2 \rangle$

$\langle s,r^4 \rangle ------ \langle r^4 \rangle$

$\langle s,r^4 \rangle ------\langle s\rangle------ \langle 1 \rangle$

Then this subgraph is homeomorphic to the graph $K_{3,3}$ with partite set $H=\{ \langle 1 \rangle,\langle r^4 \rangle,\langle s,r^2 \rangle\}$ and $K=\{\langle s,r^4 \rangle,\langle sr^2,r^4 \rangle,\langle sr,r^2 \rangle\}$. So by kuratowski's Theorem the given graph is not planar.

• I am sorry but I can't comprehend your construction. – Grobber Dec 4 '13 at 7:00
• First of all, as I can see, there is no subgroup of the lattice graph of $D_{16}$, which is isomorphic to $K_{3,3}$. So you have to look at a subgraph of the lattice graph of $D_{16}$, which is homeomorphic to $K_{3,3}$ ( or we can say, a subdivision of $K_{3,3}$. – D. N. Dec 4 '13 at 7:07
• $a------b$ denots an edge between $a$ and $b$. Please explain some more about your problem. – D. N. Dec 4 '13 at 7:14
• I have got it now. – Grobber Dec 4 '13 at 7:21

Note that the minimum size of a cycle for the graph for $D_{16}$ is four. This means, if it were to be planar, any "polygons" in the graph would have to have $4$ sides or more, and that $\frac{4}{2}f\le e$. Since $v+f-e=2$, $v-\frac12e\ge 2\Longrightarrow e\le2v-4$ must be satisfied for the graph to be planar. There are $19$ vertices and $36$ edges. $36\not\le 2(19)-4=34$, so it's not planar.

This paper is relevant.