eulerian-and-semi-eulerian-graphs

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

A vertex can be described as being odd or even:

• It has odd degree if there are an odd number of edges connected to it

• It has even degree if there are an even number of edges connected to it

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

• the sum of the degrees of the vertices is equal to two lots of the number of edges

• the number of odd vertices must 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