Eulerian Graphs (Edexcel International A Level Maths): Revision Note

The degree or valency (or order) of a vertex (node) can be defined by how many edges are incident (connected) to it

• A loop at a vertex increases the valency of a vertex by 2 as both ends of the edge are connected to it

A vertex can be described as being odd or even

• It has odd degree if there are an odd number of edge connections

• It has even degree if there are an even number of edge connections

Euler's handshaking lemma states that for any undirected graph:

• The sum of the degrees of the vertices is equal to twice the number of edges

• The number of odd vertices must therefore be even (or zero)

An Eulerian cycle starts and ends at the same vertex and traverses every edge in a graph exactly once

• Unlike a true cycle it may visit a vertex more than once

• An Eulerian cycle is also known as an Eulerian circuit

An Eulerian trail traverses every edge exactly once but starts and ends at different vertices  

• Again, vertices may be visited more than once

An Eulerian graph is a graph that contains an Eulerian cycle 

• Every vertex in an Eulerian graph has an even valency

A semi-Eulerian graph is a graph that contains an Eulerian trail

• Exactly one pair of vertices in the graph will have odd valencies

  • These odd vertices will be the start and finish points of any Eulerian trail
    

Eulerian graphs can be used to solve many practical problems where the edges should not be traversed more than once

• A common problem is the Chinese Postman problem