Revision NotesPast Papers
International A LevelMaths: Decision 1EdexcelRevision NotesAlgorithms & Graph TheoryGraphsEulerian Graphs

Eulerian Graphs (Edexcel International A Level Maths: Decision 1)

Revision Note

Naomi C

Author

Naomi C

Last updated

Degree (Valency) of a Vertex

What is meant by the degree (valency) of a vertex?

  • 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

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 twice the number of edges
    • The number of odd vertices must therefore 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

  • You can quickly tell if a graph is Eulerian or semi-Eulerian
    • Can you draw the graph without taking your pen off the paper and without going over any edge more than once?
    • If yes, 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:

    Did this page help you?

    Previous:Graph TheoryNext:Hamiltonian Graphs
    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.