How to show the following for Planar Graphs-Proof Verification

Question

Please tell me where I am wrong:

Consider this graph $G$:

Show that this graph is not planar.

My answer:

Let us consider the vertices $\{0,1,2,3,4\}$. Then the sub-graph induced by these vertices is a complete graph on $5$ vertices and hence is isomorphic to $K_5$.

We know that by Kuratowski's Theorem ,

A graph $G$ is planar if and only $G$ contains no subgraph homeomorphic to $K_5$ or $K_{3,3}$.

Since $G$ contains $K_5$ as a sub-graph , so by Kuratowski's Theorem $G$ is not planar.

NOTE:I wrote this answer in my exam and got $0$.

My professor wrote in comments "Kuratowski Theorem not applied properly , no use of homeomorphic property"

Can someone kindly say where did I go wrong in my answer? I cant figure out it myself.

If someone could kindly explain what I did wrong in my problem in the exam, I will be extremely grateful to him/her

Answer 1

Perhaps the professor wanted you to explicitly show an isomorphism between $K_5$ and the induced subgraph you picked out in $K_6$?

Here's a way to prove it without using the theorem.

A planar graph with $n$ vertices can have at most $3n - 6$ edges. Since $K_6$ has 6 vertices it would have at most 12 edges if it were planar. However, $K_6$ has 15 edges so it cannot be planar.

Answer 2

Your professors comment seems to imply that using Kuratowski's theorem is valid. You wrote that $G$ contains a subgraph that is isomorphic to $K_5$. Kuratowski's theorem says homeomorphic. Now if two graphs are isomorphic they are automatically homeomorphic. I would have given you full credit for your solution but maybe your professor wanted you to explicitly write down the last sentence showing that you knew the meaning of the different concepts.