1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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)$? $\endgroup$
    – bof
    Dec 4, 2020 at 11:46

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .