For which n=2 can you traverse every edge of the complete graph Kn exactly once and return to the start?
Quant ResearchLevel: IntermediateEuler tour feasibility
For which n>=2 can you traverse every edge of the complete graph K_n exactly once and return to the start?
Hints
- Every visit must pair entry and exit edges.
- Apply the even-degree criterion to K_n.
Answer
Exactly odd n. The graph is connected and every vertex has degree n-1. An Euler circuit requires all degrees even, so n-1 must be even; this condition is also sufficient for connected graphs.
Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial