Eulerian and semi-Eulerian graphs

Eulerian graphs

A connected graph is Eulerian if there is a route that uses every edge exactly once and returns to its start (an Eulerian cycle). This happens exactly when every vertex has even degree.

Semi-Eulerian graphs

A connected graph is semi-Eulerian if it has a route using every edge exactly once but finishing somewhere else. This happens exactly when there are exactly two vertices of odd degree; the route must start at one odd vertex and finish at the other.

Traversable

A graph that is Eulerian or semi-Eulerian is called traversable. With four or more odd vertices it is not traversable. The complete graph K_n is Eulerian when n is odd, since every vertex has degree n - 1, which is then even.

Describe precisely

Examiners want the condition stated in terms of degrees: 'all vertices have even degree' or 'exactly two vertices have odd degree'. Saying 'there are no odd vertices' is accepted only if you make it clear you mean vertices of odd degree.

Worked example

A connected graph has vertex degrees A 4, B 3, C 2, D 3, E 4. Is it traversable, and where must a route start?

1. The odd vertices are B and D: exactly two.
2. So the graph is semi-Eulerian.

Answer: Traversable: start at B and finish at D (or the reverse)

Check yourself

1. A connected graph has degrees 2, 4, 2, 4, 2. Which statement is true?
   • It is semi-Eulerian
   • It is not traversable
   • It cannot exist
   • It is Eulerian
   Show answer

   It is Eulerian. Every degree is even, so there is an Eulerian cycle.

2. A connected graph is semi-Eulerian with odd vertices P and T. Where must a route using every edge once start and finish?
   • At any vertex, returning to it
   • At P and T
   • At P, finishing at P
   • At any two even vertices
   Show answer

   At P and T. An Euler route through a semi-Eulerian graph must start at one odd vertex and end at the other.

3. Find the value of n with 4 < n < 7 for which K_n is Eulerian.
   Show answer

   5. In K_n every degree is n - 1. For n = 5 this is 4, which is even, so K_5 is Eulerian. For n = 6 every degree is 5, which is odd.

4. A connected graph has degrees 4, 3, 2, 3, 4. How many vertices have odd degree?
   Show answer

   2. B and D have degree 3; the rest are even.

5. Why is K_6 not traversable?
   • It is not connected
   • It has an odd number of edges
   • All six vertices have odd degree 5
   • It has six even vertices
   Show answer

   All six vertices have odd degree 5. Each vertex of K_6 has degree 5. Six odd vertices is more than two.

6. The Königsberg bridges problem has four land areas with degrees 5, 3, 3, 3. What does this show?
   • No walk can cross every bridge exactly once
   • There is a closed walk crossing every bridge once
   • There is an open walk crossing every bridge once
   • One more bridge would make it Eulerian
   Show answer

   No walk can cross every bridge exactly once. Four odd vertices: not Eulerian and not semi-Eulerian.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics specification (issue 3)
• Pearson Edexcel IAL Decision Mathematics 1 scheme of work

Last updated 7 November 2026. Spotted a mistake? Tell us.