Prove that a series-parallel hamiltonian graph is outerplanar.

119 Views Asked by At

A graph is series-parallel (SP) iff it contains no $K_4$ minor. I know that if the graph has no $K_4$ or $K_{2,3}$ minors, it is outerplanar. So maybe there is a way to use the fact that it is hamiltonian to prove that the graph has no $K_{2,3}$ minor.

Or maybe there is another way: since $K_5$ and $K_{3,3}$ contain $K_4$ minors, the graph cannot contain these minors and hence is planar by kuratowski's theorem. And then somehow the fact that the graph is hamiltonian shows that is outerplanar.

Any guidance on how to complete these thoughts is appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Start by drawing the hamiltonian cycles in the plane. Then add the all chords inside the cycle. Note that there will be no crossing edges because crossing edges imply $K_4$ minor.