Discrete Math › Section C · Graph theory › Topic C.5
Euler trails and Hamilton paths
A snowplough wants to clear every street once; a delivery van wants to call at every address once. The first question, about edges, has a complete and simple answer. The second, about vertices, is one of the hardest problems in computing.
In this topic
- Seven bridges
- Euler trails and circuits
- Why degrees decide it
- Euler's theorem
- Worked example: tracing a trail
- Worked example: fixing Königsberg
- Hamilton paths and cycles
- A guarantee: Dirac's theorem
- Worked example: proving there is no Hamilton cycle
- The travelling salesperson problem
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…