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. enter image description here

And to add one more question, are there any interesting implication of planarity in group theory?

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

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.

  • $\begingroup$ I am sorry but I can't comprehend your construction. $\endgroup$ – Grobber Dec 4 '13 at 7:00
  • 1
    $\begingroup$ 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}$. $\endgroup$ – D. N. Dec 4 '13 at 7:07
  • $\begingroup$ $a------b$ denots an edge between $a$ and $b$. Please explain some more about your problem. $\endgroup$ – D. N. Dec 4 '13 at 7:14
  • $\begingroup$ I have got it now. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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