Problem
COM-B2-M07-P018 Criterion for an Euler Trail
Prove that a connected graph has a trail using every edge exactly once if and only if the number of vertices of odd degree is \(0\) or \(2\).
Necessity is known. For two odd vertices, add a new edge between them.
Necessity follows from entry-exit pairs: only the start and end of a non-closed Euler trail may be odd, while an Euler circuit has no odd vertices.
For sufficiency, if there are no odd vertices, the lemma on even degrees in a connected graph gives an Euler circuit.
If there are exactly two odd vertices, call them \(a\) and \(b\). Add a new edge \(ab\). Now all degrees are even, so the new graph has an Euler circuit. Remove the added edge from this circuit. The remaining sequence of edges is an Euler trail of the original graph from \(a\) to \(b\).
The full Euler trail criterion at Book 2 level.