Lecture 18 · Mathematics
Euler tours
Use every edge once
Video in production
This lecture is still face down. Its script is written; filming and animation are under way.
Meanwhile, read the outlineWhat you will learn
Prove Euler-tour existence under directed balance and connectivity and apply it to de Bruijn graphs.
Before this lecture
Ideas you will use
- Word-edge correspondence
In this lecture
An outline of the lecture, scene by scene, with the statements that appear on screen. It follows the draft script, so details may change in production.
Clarify Euler target with small contrast
- Euler tour: every edge once; closed
- Balance +directed connectivity
- Construct, then splice
Show necessity of degree balance
- indegree(v)=outdegree(v)
- Loop: adds 1 to each degree
- Two isolated cycles: balanced but not one tour
Prove unused-edge walk can only stop at its start
- At non start endpoint: used-in=used-out+1
- Balance ⇒an unused exit remains
- A closed trail may be partial
Find unused edge incident to existing tour
- Unused edges remain ⇒attachment vertex exists
- Removing a closed trail preserves balance
- Second trail uses only unused edges
Explain splicing without an invalid jump
- Pause outer trail
- Follow closed inserted trail
- Resume at the same vertex
Verify de Bruijn hypotheses generally
- 2 incoming; 2 outgoing
- Append target context to reach it
- Euler tour ⇒de Bruijn cycle
Companion graph repair tasks
- Check continuity
- Check coverage
- Check closure
Reconstruct proof and state exact theorem
- Balanced +strongly connected ⇒Euler tour
- Edges are observations
- Closure protects the join
Companion interactive
Planned
Construct and justify an Euler tour or identify an obstruction.
The interactive for this lecture is being built and will appear here.
Notes
Written notes for this lecture will appear here.
Sources
- Magical Mathematics, pp. 20–24
How these sources were used
- Eulerian construction; expanded cycle-splicing proof supplied for teaching.