Eulerian & semi-Eulerian Graphs

Order (Degree) of a Node

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)

pYOJ_rS-_valency-or-degree-of-nodes

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

If you can draw a graph without taking your pen off the paper and without going over any edge more than once then you have an Eulerian or semi-Eulerian graph!

Let G be the graph shown below.

3-10-4-ib-ai-hl-chinese-postman-problem-we-1

Show that G is a semi-Eulerian graph.

Look at the degree of each vertex.

A: 2

B: 4

C: 3

D: 3

E: 4

G is a semi-Eulerian graph because it has exactly one pair of odd vertices, C and D

Write down an Eulerian trail for G.

An Eulerian trail must start and end at C/D

There are several possible Eulerian trails, one solution is

DEABECDBC