How to apply Kuratowski's theorem here

811 Views Asked by At

I'm unsure which subgraph to find and which of $K_{3,3}$ or $K_5$ I should compare it to. First this looks like $K_6$. If it was $K_6$, I could simply remove one of the vertices to get $K_5$ and I would be done.
However, there is an extra vertex $I$ in the centre. I thought of removing a vertex say $B$ and then removing edge $IE$ to get $K_5$ with an extra vertex in the middle. Then I'm unsure here because it doesn't seem that this is a subdivision of $K_5$... (the middle point seems like a subdividing vertex for more than one edge)

2

There are 2 best solutions below

3
On BEST ANSWER

Consider the union of the path $FEDC$ and the graph induced by vertices $A,B,C,I,F$. This subgraph is a subdivision of $K_5$.

0
On

$A$ is joined to $C,E,F$, also $D$ is joined to $C,E,F$, and $B$ is joined to $C$ and $F$, and to $E$ via $I$, so there's also a $K_{3,3}$ there.