Is this graph a planar graph?

198 Views Asked by At

I am required to prove if this is planar or not.

Graph

This is what I have tried. I have tried to form a $K_{3,3}$ or $K_5$ but I am unsucessful so far. I have also tried to use the formulas $e ≤ 3n - 6$ where $e$ = number of edges, $n$ = number of vertices, but it didn't help.

2

There are 2 best solutions below

2
On BEST ANSWER

Can you drag vertex $1$ somewhere that will reduce crossings? How about $3$?

Edit: Looking at it again, the fastest way to a pretty picture is to swap $2$ with $5$.

0
On

Just wish to add that there is a subtle point to this problem, and that is, "What constitutes a legitimate subdivision of a graph?"

As dfeuer astutely points out, switching the positions of vertices 2 and 5 gives a planar embedding of the indicated graph. However, according to theory, any subdivision of $K_{3,3}$ is non-planar. The point is, one may be misled into believing that the indicated graph is a legitimate subdivision of $K_{3,3}$. It's not, since in a subdivision only a single edge can be subdivided at a time.