Let $G=(V,E)$ be a graph. Assume that $G$ contains at least three vertices with an odd degree. Show that there can be no trail in $G$ that contains all edges.
First I checked the definition of a trail; that is a walk that does not contain any edge more than once. I tried reasoning by contradiction, assuming that there is a trail that contains all edges. Then there should exist a trail s.t. $v_0\rightarrow v_1 \rightarrow \dots \rightarrow v_n$ where every edge is unique. However, I am stuck here.
Could anyone please give me a hint to this problem and most of all give me advice on how to approach these kind of graph theory proofs in general? Thank you in advance!
HINT: Consider a vertex $v$ that is neither the first nor the last vertex of a trail $T$. $T$ may pass through $v$ more than once, but each time $T$ passes through $v$, it ‘uses up’ two edges incident at $v$: one on the way in, and one on the way out. If $T$ contains every edge of the graph, those must be all of the edges incident at $v$, so $v$ must have even degree.
I can’t really offer any general advice. In this problem the at least $3$ in the problem statement might suggest that with just two odd vertices there could be a trail that contains all of the edges, and a bit of experimentation with small graphs would tend to confirm that. You’d probably also discover just where on the trail the odd vertices always seem to end up, which could well point you in the right direction.