I'm working in the following graph theory excercise.

Prove or disprove that If $G$ is a graph with one or more triangles and contains no subdivision of$ K_5$ as a subgraph, then $G$ is planar.

I'm thinking about the graph $K_6$ and how is non-planar by Kuratowski's theorem, so the answer would be that the statement is false. But I'm not sure about what does "no subdivision of$ K_5$ as a subgraph" means, any hint or help will be really appreciated.


Subdivisions are defined here; essentially you can subdivide a graph by adding extra vertices along edges (as you choose). This adds a bunch of extra vertices with degree $2$.

When the question says the graph "has no subdivision of $K_5$", it means that no subgraph of the graph is of this form. As a non-example, $K_6$ indeed has a subdivision of $K_5$, as if we remove $3$ edges coming from a single vertex (so that it now has degree $2$), then the resulting graph is a subdivision of $K_5$.

To give you a hint, if this were true, then we could take any non-planar graph without a subdivision of $K_5$, add in three extra vertices connected in a triangle but disconnected from the rest of the graph, and suddenly it would be planar. That is, every graph with a subdivision of $K_5$ would have to be non-planar. Compare this with Wagner's Theorem (often mistakenly attributed to Kuratowski), to find a non-planar graph without a $K_5$ subdivision, and use it as above to form a counterexample.

| cite | improve this answer | |
  • $\begingroup$ @MishaLavrov Thanks. $\endgroup$ – Theo Bendit Mar 9 '19 at 21:27

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.