Problem
COM-B2-M07-P012 Necessary Condition for an Euler Trail
#12
★★★☆☆ Level 3 of 5
A connected graph has a trail using every edge exactly once. Prove that the number of vertices of odd degree is \(0\) or \(2\).
Every intermediate visit to a vertex pairs an entering edge with a leaving edge.
If the trail is not closed, then at every internal vertex the used edges are paired: enter and leave. Thus internal vertices have even degree. Only the start and end may have odd degree.
If the trail is closed, then at the starting vertex entrances and exits also pair up, so all degrees are even. Hence the number of odd-degree vertices is either \(0\) or \(2\).
Needed for the full Euler trail criterion.