Revision NotesExam QuestionsPast Papers
A LevelFurther Maths: Decision Maths 1EdexcelRevision NotesAlgorithms & Graph TheoryGraphsEulerian & semi-Eulerian Graphs

Eulerian & semi-Eulerian Graphs (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note

Naomi C

Author

Naomi C

Last updated

Order (Degree) of a Node

What is meant by the 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

What is Euler's handshaking lemma?

  • 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

Eulerian & Semi-Eulerian Graphs

What are Eulerian cycles and trails?

  • 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

What are Eulerian and semi-Eulerian graphs?

  • 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

Examiner Tip

  • 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!

Worked example

Let G be the graph shown below.

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

a)
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 

b)
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

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

    Test yourself

    Did this page help you?

    Previous:Graph TheoryNext:Planarity Algorithm
    Naomi C

    Author: Naomi C

    Expertise: Maths

    Naomi graduated from Durham University in 2007 with a Masters degree in Civil Engineering. She has taught Mathematics in the UK, Malaysia and Switzerland covering GCSE, IGCSE, A-Level and IB. She particularly enjoys applying Mathematics to real life and endeavours to bring creativity to the content she creates.