1
$\begingroup$

So,

Kuratowski theorem tells us that a graph G is planar iff it does not contain a $K_{5}$ or $K_{3,3}$ minor,

enter image description here

Is non planar because

enter image description here

I am not really sure how to understand the red drawing. It says it shows a $K_{3,3}$ minor. But is it doing some sort of edge/vertex deletions? What would the bipartition be?

Also,

enter image description here

is planar because it has a planar drawing. So isnt the drawing with vertex g removed the planar graph?

So basically, I am generally confused in the difference between having a minor and a subdivison , and which implies the other.

I know that a subgraph of a planar graph is planar, and if a subgraph is non planar then the graph is non planar. But a subgraph can be planar while the original graph is still non planar, I guess that is what is showcased in this example.

But mostly I am confused about the diagram and what the red represents.

Thanks

$\endgroup$
1
$\begingroup$

Contracting the two red edges leaves $K_5$, showing that the graph is not planar.

We can find a $K_{3,3}$ minor by contracting the bottom edge $ef$. One side of the partition of the $K_{3,3}$ minor is $\{a,b,g\}$.

$\endgroup$

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.