Is a cycle for a graph containing all edges of the graph necessarily an Euler cycle?

Question

Under the definition that an Euler cycle is a cycle passing every edge in G only once, and finishing on the same vertex it begins on.

I have reasoned that the answer to this would be no, since it seems reasonable to argue that if we construct a connected graph $G = (V,E)$ such that $|V| < |E|$ containing some cycle $C$ where $\forall e\in E(G), e \in C$.

Via the Pigeonhole Principle, $C$ can not be an Euler cycle since there must be some edge $e \in C$ which is visited more than once, so $C$ is not an Euler cycle, however C does contain every edge.

This seems mostly reasonable however I cant shake the feeling that this proof is slightly shaky, if there is something missing with this proof some clarity would be amazing.

Thank you!

Answer 1

(I will switch to the more modern terminology and call these these things "closed walks"; these days, "cycle" refers to the kind of closed walk that does not come back to a vertex more than once.)

Your proof is shaky, and the reason for that is you're trying to prove that $C$ cannot be an Eulerian tour, using nothing more than the fact that $C$ is a closed walk containing every edge. This can't possibly work - after all, some closed walks really are Eulerian tours!

Stop before you get into details like that and ask yourself what you really have to prove. The negation of

Every closed walk containing all the edges of an graph $G$ is necessarily an Eulerian tour

is actually

There is a graph $G$ and a closed walk containing all the edges of $G$ which is not an Eulerian tour.

You only have to give a single example to prove this! Just draw a graph (any connected graph will do) and find a closed walk in the graph that contains all the edges, but which is not an Eulerian tour. That is enough to know that the statement is false.

For a more abstract kind of statement, we might prove that every connected graph $G$ has a closed walk which contains all its edges but has no Eulerian tour. This requires more work, though.

Here's one way to do it. Take your connected graph $G$, and replace each edge by two edges between the same vertices. This gives a multigraph in which every degree is even, so it has an Eulerian tour. That Eulerian tour corresponds to a closed walk in $G$ in which every edge is used twice - definitely not exactly once!