3
$\begingroup$

I need to show whether the following graph $G$ is planar or not. Graph on 6 vertices.

At my first glimpse, it looks like a non-planar graph. Nevertheless, I couldn't find any subgraph homeomorphic to $K_5$ or $K_{3,3}$. As a consequence, I turned to prove it to be a planar graph. Below is my proof.

First we prove that $G$ doesn't contains a subgraph homeomorphic to $K_5$. We cannot perform smoothing on $G$ as there doesn't exist a vertex of degree $2$. By subdivision, we could only create vertices of degree $2$. But there are only two vertices whose degree are greater than or equal to $4$, thus we cannot select a subgraph which is $K_5$.

Then we show that $G$ doesn't contains a subgraph homeomorphic to $K_{3,3}$. Since the sets of neighbors of 3-degree vertices are not either identical or complement, we cannot form a such bipartite.

Hence by Kuratowski's theorem, $G$ is a planar graph.

Could anybody please kindly help me verify the correctness of my proof? Thanks!

$\endgroup$
2
  • $\begingroup$ Hint: you can redraw $G$ as a pentagonal wheel graph (pentagon with spokes to the center) with one extra edge connecting a pair of non-adjacent vertices around the rim. $\endgroup$
    – Sammy Black
    Commented May 31 at 21:58
  • $\begingroup$ Indeed, that would be my approach if I had a blank piece of paper in front of me; but the question was whether the Kuratowski argument is valid as presented here. $\endgroup$
    – Lieven
    Commented May 31 at 22:02

2 Answers 2

Reset to default
1
$\begingroup$

Essentially, this is an acceptable strategy. Your argument that there is no $K_{3,3}$ subgraph could be a bit more explicit, for example: surely you mean to look at vertices of degree at least 3 (because we want to exclude the existence of subgraphs)?

Alternatively (but that was not your question) you could shift the positions of a few vertices to make it visibly planar. The lower right vertex goes to the far upper left, the lower left vertex moves to the centre and the upper right one move slightly lower and to the left.

$\endgroup$
1
  • $\begingroup$ Thanks for your explanation! $\endgroup$
    – nevikw39
    Commented Jun 1 at 7:50
1
$\begingroup$

A pictorial proof that $G$ is a planar graph: enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Oh thanks! I spent lots of time trying to draw it as a planar graph but in vain $\endgroup$
    – nevikw39
    Commented Jun 1 at 4:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .