Foundation to VCE • Explore the maths library • Try a free sample
VCE General Mathematics Units 3–4 · Discrete mathematics

Network traversal and shortest paths

An Euler trail uses each edge once; a Hamiltonian path visits each vertex once. These answer different travel questions.

3 printable resources11 pages12 questionsWorked answers
A$3.90Planned launch price · including GST
One household or one teacher’s own classes
Preview available. Checkout opens soon.The full topic collection is prepared. Explore a sample before choosing.

What you’ll work on

  • Graphs and networks
  • Exploring and travelling problems
  • Shortest path problems

Start with the idea

An Euler trail uses each edge once; a Hamiltonian path visits each vertex once. These answer different travel questions.

In a connected undirected graph, an Euler circuit requires all vertex degrees even; an open Euler trail has exactly two odd vertices. Dijkstra’s algorithm finds shortest routes with non-negative weights.

A worked example

A connected undirected graph has degrees 2, 2, 3, 3. Does it have an Euler trail or circuit?

  1. Exactly two vertices have odd degree
  2. these are the trail endpoints.

Answer: An open Euler trail, no Euler circuit.

Try one question

A connected undirected graph has degrees 4, 2, 2, 2, 2. What Euler traversal exists?

Show answer and explanation

An Euler circuit.

All degrees are even and the graph is connected.

Inside the collection

ResourceLengthPracticeAnswers
Learn and practise4 pages4 questionsIncluded
Apply and extend4 pages4 questionsIncluded
Topic checkpoint3 pages4 questionsIncluded

Read on a device and work in an exercise book, or print the A4 PDFs. These files are not auto-marked digital quizzes.