Proving or disproving planarity

Question

I'm looking through past exams and am having issues on this problem:

Call the graph $G$. My immediate thought is to use brute-force. That is, I want to apply Kuratowski's Theorem and find a subgraph of $G$ which happens to be an edge-subdivision of $K_5$ or $K_{3, 3}$ to prove that $G$ is not planar. The issue is, I've been at it for a bit with no success.

Is there a more directed approach I may take? Is there a hint that $G$ is planar or not hidden in plain sight? Thanks in advance!

Answer 1

Redraw our graph in five steps.

Note first that

all vertices of a planar graph and all its edges must lie inside (or outside) any triangle face (except vertices and sides of this triangle).

1. Choose some triangle, say $136$. We will make it all lie inside triangle $136$.

2. We move the vertices $3$ and $6$ so that the vertices $4$ and $5$ are inside triangle $136$.

3. We see that quadrangle $3546$ has intersecting sides. Rearrange the vertices $4$ and $5$ and raise them higher at the same time.

4. Now move the vertex $7$ inside triangle $136$ .

5. It remains to move the vertex $2$.

Answer 2

You should use Kuratowski's theorem

a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ or of $K_{3,3}$

You can use Mathematica to get the answer:

g = Graph[{1 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 5, 
   2 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 5, 
   2 \[UndirectedEdge] 7, 3 \[UndirectedEdge] 5, 
   3 \[UndirectedEdge] 7, 4 \[UndirectedEdge] 5, 
   4 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 7, 
   5 \[UndirectedEdge] 7, 6 \[UndirectedEdge] 7}, 
  VertexLabels -> "Name", GraphLayout -> "PlanarLayout"]
PlanarGraphQ[g]  (*PlanarGraphQ[g]=True*)