Further Maths - Eulerian Trails
See Also
Flashcards
What is a Eulerian trail?
A trail that goes along every edge exactly once.
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.
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.
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.
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.
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.