Does this graph contain a subdivision of $K_5$ or $K_{3,3}$?

41 Views Asked by At

I'm working on graph theory and I've encountered a challenge in determining whether a given graph contains a subdivision of $K_5$ or $K_{3,3}$, which would imply that the graph is non-planar by Kuratowski's theorem.

I have a graph (attached below) with 11 vertices and a number of edges, and I am unsure how to identify such subdivisions effectively.

Could someone assist in checking whether this graph has a subdivision of either $K_5$ or $K_{3,3}$ and explain the methodology for identifying such a subdivision? Understanding the process would greatly aid in my comprehension of non-planar graphs and Kuratowski's theorem. I looked at other questions and I tried to identify vertices of degree 4, which would be the original vertices of $K_5$ in its subdivision for example but I'm not sure.

Here's the graph:

enter image description here

Any insights or strategies for identifying these subdivisions would be highly appreciated!

1

There are 1 best solutions below

0
On

I'm sure there are many ways to view this, but one I came up with was by collapsing $3,7,10,11$ all into one vertex, and collapsing $1,5,8$ into one vertex.

The resulting graph before collapse could be viewed as the following:

enter image description here

Actually performing the collapsing

enter image description here

Here we can see $K_{3,3}$, albeit with more edges. $4,6,9$ on one part and $1,2,3$ in the other part with edges between.

In fact, by going further and collapsing $2$ with $9$ we can also rearrange to find $K_5$ present as well. enter image description here