I'm trying to disprove the statement that "If a graph $G$ does not have a $K_{3,3}$ or a $K_5$ as an induced subgraph, then it is planar" by counterexample. I'm thinking that I can just use the Petersen graph as a counterexample and say that the Petersen graph has neither a $K_{3,3}$ nor a $K_5$ as an induced subgraph, but it is non-planar by Kuratowski's theorem.

Is this sufficient to disprove the claim?


This is sufficient as long as you justify the fact that the Petersen graph has neither $K_{3,3}$ nor $K_5$ as an induced subgraph. It has no vertex of degree $4$, so the $K_5$ half is clear, but the $K_{3,3}$ half is (slightly) more difficult.

Or you could start with some subdivision of $K_{3,3}$ in place of the Petersen graph.

| cite | improve this answer | |

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.