Vertex parity principle explains feasibility of one-pass traversal. A closed one-pass route needs all vertices even because every arrival must be matched by a departure. If odd vertices exist, additional traversals are required to balance these unmatched incidences.
Handshake lemma guarantees odd vertices come in pairs, which is why pairing strategies are possible. The identity forces the number of odd-degree vertices to be even. This gives the mathematical basis for adding paths between odd vertices.
Cost decomposition separates fixed and variable parts of the answer. Let be the sum of original edge weights and the minimum extra repeated weight needed to satisfy route constraints; then
Key formula: This works because every original edge must be covered at least once, and only repeated edges create extra cost.
| Situation | Repetition needed? | Route form |
|---|---|---|
| All vertices even, closed route | No | Eulerian circuit |
| Exactly 2 odd vertices, closed route | Yes: shortest path between odd pair | Circuit on adjusted graph |
| Exactly 2 odd vertices, open route from one odd to the other | No | Eulerian trail |
| More than 2 odd vertices, closed route | Yes: minimum-total pairing of odd vertices | Circuit on adjusted graph |
Shortest direct edge vs shortest path is a critical distinction in weighted graphs. The edge with smallest local weight may not solve the parity correction optimally if a multi-edge path has lower total cost. Route inspection always optimizes by path weight, not by geometric directness.
Covering all edges vs shortest path between two vertices are different problem families. Route inspection is an edge-coverage optimization, while standard shortest-path problems are endpoint-to-endpoint optimization. Mixing these objectives leads to incorrect algorithms and undercounted route cost.
Start by listing degree parity clearly before attempting any route writing. This prevents wasted time constructing invalid circuits on non-Eulerian graphs. A quick parity table also exposes whether duplication is needed and how much analysis remains.
When pairing odd vertices, compare totals systematically rather than choosing the first plausible pair. Examiners often design weights so an indirect combination beats an obvious-looking direct option. Show shortest-path calculations for each candidate pairing to secure method marks.
Use a final verification routine after proposing a route. Confirm every original edge is covered at least once, repeated edges match your planned duplication, and the final start/end condition is satisfied. Then recompute total weight as original sum plus repeated sum to catch arithmetic slips.
Pitfall: minimizing number of repeated edges instead of repeated weight causes non-optimal answers. Two repeated edges can be worse than three if their total weight is larger. The objective function is weighted cost, so every decision must be cost-based.
Pitfall: forgetting route-condition context leads to unnecessary duplication. If an open route is allowed and there are exactly two odd vertices, starting and ending at the odd pair can avoid added paths entirely. Applying closed-route logic blindly overestimates the minimum route.
Pitfall: constructing a plausible walk without proving optimality loses marks in formal settings. A valid traversal is not enough unless the repeated-path choice is justified as minimal. Always separate feasibility proof (can traverse all edges) from optimality proof (least total weight).
