# Characterizing graphs for which the subdivision graph S(G) is Eulerian or Hamiltonian

I know that $$G$$ is Eulerian iff all of the vertex degrees are even. So my thinking is that for any cycle graph $$C_n$$, its subdivision graph is Eulerian because each vertex has degree 2 and adding a new vertex at each edge doesn't change that. But I think my professor wants a more comprehensive answer. For the bipartite graph $$K_{n,m}$$ the subdivision graph will be Eulerian if $$n$$ and $$m$$ are both even so that the degree of all vertices is even.

From this, is it safe to say that the requirement for $$S(G)$$ being Eulerian is that $$G$$ is Eulerian? Am I missing something?

Would it also be correct to say that the requirement for $$S(G)$$ being Hamiltonian is that $$G$$ is Hamiltonian?

• I believe you're right about Eulerian, but I have my doubts about Hamiltonian. Why don't you take some small Hamiltonian graph $G$ that's not just a cycle, and try to find a Hamiltonian cycle in $S(G)$?
– bof
Dec 4, 2020 at 11:46

I'm going to assume $$S(G)$$ is $$G$$ with every edge subdivided. Let $$|G| = |V(G)|$$ and $$||G|| = |E(G)|$$.

$$G$$ is Eulerian if and only if $$S(G)$$ is Eulerian.

Subdividing an edge adds a vertex of degree $$2$$ and preserves all other degrees, and thus if $$G$$ is Eulerian $$S(G)$$ is Eulerian. If $$S(G)$$ is Eulerian, suppose $$G$$ is not Eulerian. Find a contradiction.

If $$G$$ is Hamiltonian (has a Hamiltonian cycle), then it is not necessarily the case that $$S(G)$$ is Hamiltonian.

Can you find infinitely many examples? Here's one: $$K_4$$.

In order to characterize you need to make a few observations.

Suppose $$S(G)$$ is Hamiltonian and let $$C$$ be a Hamiltonian cycle in $$S(G)$$. Note, $$S(G)$$ replaces each edge $$uv$$ of $$G$$ with a vertex $$a$$, and adds edges $$ua,av$$. Let $$A\subseteq S(G)$$ be the set of all such $$a$$. For every $$a \in A$$, we have $$\deg_{S(G)}(a) = 2$$. We know $$C$$ must use $$|S(G)|$$ edges. Simultaneously, $$C$$ must use every edge with an end point in $$A$$ (why?). Conclude from this that $$|S(G)| = |C| = ||S(G)||$$ and thus $$S(G)$$ is a cycle, and thus $$G$$ is a cycle.

For your last question, if I understand it correctly.

If $$S(G)$$ is Hamiltonian, then $$G$$ is Hamiltonian.

Hint: Find a Hamiltonian cycle in $$S(G)$$, how can you extend this to a Hamiltonian cycle in $$G$$.