Is a subdivision of a Hamilton Graph, a Hamilton Graph too?

80 Views Asked by At

How would I go about showing this? I think the answer is yes, as subdividing a graph doesn't affect the cycles it has: When going from node a to b, a subdivision of 1 will for example simply make you go from a to v to b. But I'm missing an insight to formally show this.

1

There are 1 best solutions below

0
On

In fact there is a Hamiltonian graph $H$ whose subdivision is not Hamiltonian.

Hint: Let $v_1v_2 \ldots v_7$ be a $7$-cycle. Then add the vertex $y_1$ and the edges $v_7y_1$ and $y_1v_1$. Draw this out; $v_1v_2 \ldots v_7$ is a $7$-cycle and $v_7y_1v_1$ form a triangle. Then this resulting graph $H$ has $8$ vertices and a Hamiltonian cycle $v_1v_2 \ldots v_7y_1$.

What if you were to subdivide each of the edges $v_7v_1, v_7y_1$ and $y_1v_1$ of $H$ however? Is the resulting graph still Hamiltonian? [You should see that the answer is No.]