Further Maths - Eulerian Trails
Pearson Edexcel Further Mathematics 2022
See Also
Flashcards
Defining Eulerian trails and cycles
Why isn’t a trail that visits every edge multiple times a Eulerian trail?
Because it visits an edge more than once.
What is a Eulerian trail that joins up to the beginning called?
A Eulerian cycle.
Conditions for a Eulerian trail
How many edges does entering a vertex and then exiting a vertex “use up” when constructing a Eulerian trail?
2
Why must all vertices be even for a Eulerian trail to be possible?
So that there is always a new path in and out of a vertex.
What is the technical condition for a graph to contain a Eulerian trail?
The order of all the vertices are even.
Eulerian and semi-Eulerian graphs
What does it mean for a graph to be “Eulerian”?
There is a Eulerian trail on the graph.
What does it mean for a graph to be “semi-Eulerian”?
It is possible to cover all edges without repeats starting at one vertex and ending at another.
What is the technical condition for a graph to be “semi-Eulerian”?
It must have all even vertex orders apart from two odd vertices.
Traversability
What is the technical condition for a graph to be traversable?
It is Eulerian or semi-Eulerian.
What does it informally mean for a graph to be traversable?
You can draw the graph without taking your pencil off the paper and without repeating any edges.
The Konigsberg bridge problem
What was the Konigsberg bridge problem?
Trying to cross each bridge exactly once and trying to end up back where you started.
What was the technique used to solve the Konigsberg bridge problem?
Representing it as a graph and showing it is not Eulerian.