I am trying to prove: Except for $K_{3,3}$ itself, no expansion (aka subdivision) of $K_{3,3}$ is a supergraph of $K_{3,3}$.
Does the following look valid? Is there a better solution?
Proof: Suppose there was such a (proper) supergraph with a single vertex expanded. Then, for any selection of 6 vertices we can make there are two cases to consider:
- Case 1: We chose 6 vertices, none of which is an expanded vertex of degree 2. In this case, we have $v = 6$ and $e = 8$, which cannot be isomorphic to $K_{3,3}$.
- Case 2: We chose 6 vertices, at least one of which is a vertex of degree 2, which means it cannot be isomorphic $K_{3,3}$.
In cases where there are more than one expansion, we have two similar cases: We either end up with $e \leq 8$ or vertices of degree two.
Therefore, no such supergraph exists.