Eulerian and Hamiltonian graphs
Walking every edge once (Eulerian trails and circuits, Euler's theorem, the Königsberg bridges, the Chinese postman) or every vertex once (Hamiltonian paths and cycles, the travelling salesman): two neighbouring questions, two very different difficulties.
- 30 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Eulerian trail: what is it?
Show the answer
A walk that uses each edge of the graph exactly once, but may pass through the same vertex several times.
It is the “single stroke without lifting the pen” drawing. A vertex may be revisited, an edge never.
What does this program print? It describes the seven bridges of Königsberg.
```python
bridges = [("A", "C"), ("A", "C"), ("B", "C"), ("B", "C"), ("A", "D"), ("B", "D"), ("C", "D")]
degree = {}
for u, v in bridges:
degree[u] = degree.get(u, 0) + 1
degree[v] = degree.get(v, 0) + 1
print(sum(1 for d in degree.values() if d % 2 == 1))`4027
Show the answer
4The degrees are A = 3, B = 3, C = 5, D = 3: all four are odd. An Eulerian trail allows at most two, so you cannot cross each bridge exactly once. 7 is the number of bridges, not of odd vertices.
A connected graph has an Eulerian circuit if and only if all its vertices have … degree.
Show the answer
A connected graph has an Eulerian circuit if and only if all its vertices have even degree.
Each time you go through a vertex you enter by one edge and leave by another: edges are used up in pairs.
Eulerian circuit: what is it?
Show the answer
A closed Eulerian trail: it returns to its starting vertex after using each edge exactly once.
You may start from any vertex, since the tour comes back to its starting point.