Skip to main content
MathidiaMathematics Academy
Graph theory and networks
Lesson 47 of 75
Easy practice

Eulerian and Hamiltonian structure

Objective. Distinguish traversal and spanning-cycle problems.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

Eulerian and Hamiltonian structure distinguishes two different ways a graph can be traversed: an Eulerian circuit uses every edge exactly once and returns to its start, while a Hamiltonian cycle visits every vertex exactly once and returns to its start. A connected graph has an Eulerian circuit if and only if every vertex has even degree, by Euler's theorem; no simple general criterion exists for Hamiltonian cycles, making them far harder to detect. For example, the complete graph K₄ has all vertices of degree 3 (odd), so it has no Eulerian circuit, yet it clearly has a Hamiltonian cycle such as 1-2-3-4-1. Confusing 'every edge once' with 'every vertex once' is the key distinction to keep straight.

Worked example

A connected graph has vertices of degrees 2, 2, 2, 4. Determine whether it must contain an Eulerian circuit, using Euler's theorem.

2 … 2
Coordinate grid with the line 2 … 2
  1. 1Euler's theorem: a connected graph has an Eulerian circuit iff every vertex has even degree.
  2. 2List the degrees: 2, 2, 2, 4.
  3. 3Check parity: all four degrees are even.
  4. 4Since the graph is connected and all degrees are even, it must contain an Eulerian circuit.

Answer: Yes, it must contain an Eulerian circuit

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students assume a graph with a Hamiltonian cycle must also have an Eulerian circuit (or vice versa); these properties are independent, so K₄ has a Hamiltonian cycle but no Eulerian circuit, since its vertices have odd degree.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard