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.
Best Answer
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.