Give an example of a graph $G$ such that $G$ and $G'$ are not Eulerian, but $G$ has an Eulerian trail and $G'$ does not have an Eulerian trail.

Question

Give an example of a graph $G$ such that $G$ and $G'$ are not Eulerian, but $G$ has an Eulerian trail and $G'$ does not have an Eulerian trail.

I was thinking that $T_n$ is not Eulerian but it does contain an Eulerian trail. On the other hand $T_n'$ is not Eulerian and does not contain an Eulerian trail. Is this correct?

Answer 1

Recall that a connected graph has an Eulerian cycle, if and only if all its vertices have even degree and an Eulerian trail, if and only if all vertices besides exactly zero or exactly two have even degree.

Using this characterization one immediately sees that

• The cycles $C_n$ are graphs with an Eulerian cycle, and hence Eulerian trails as well.
• The paths $P_n$ are graphs without an Eulerian cycle but with an Eulerian trail.
• The stars $S_n$ with $n\geq 3$ neither have an Eulerian cycle nor an Eulerian trail. In fact any tree with more than two leaves does the job.

Answer 2

Take $G=K_4$ but with any two edges removed. Take $G'$ to be the star graph $S_3$.

Since $G$ is connected and has a vertex with degree three, then $G$ cannot contain an Eulerian circuit, and so is not Eulerian. $G'$ is not Eulerian for the same reason.

There is an Eulerian trail in $G$, a path that visits every edge exactly once, but there is not one in $G’$.