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

Teach network traversal and shortest paths.

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

View worksheets & preview

Aspire to Power Learning · https://resources.aspiretopowerlearning.com.au/home-learning/topics/general-3-4-network-travel/

Check the starting point

  • Distinguish vertices from edges.
  • Add route weights and respect edge directions.

Show the idea

Compare routes using edge weights

A–C–B–D has length 1+2+1=4. An Euler task instead asks about using every edge; a Hamiltonian task asks about visiting vertices.
Select the diagram to view it at full size.

A–C–B–D has length 1+2+1=4. An Euler task instead asks about using every edge; a Hamiltonian task asks about visiting vertices.

Work through an example

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

  1. The graph is connected, satisfying the connectivity requirement for an Euler traversal.
  2. The degrees 2,2,3,3 contain exactly two odd entries. An open Euler trail starts at one odd-degree vertex and ends at the other.
  3. An Euler circuit would require every degree to be even. Hence there is an open trail but no circuit.

Answer: An open Euler trail, no Euler circuit.

Teach in small steps

  1. Read the visual model together: A–C–B–D has length 1+2+1=4. An Euler task instead asks about using every edge; a Hamiltonian task asks about visiting vertices.
  2. Model this example aloud: A connected undirected graph has degrees 2,2,4,4,6. What Euler traversal exists? Guide: Every degree is even and the graph is connected, so all edges can be used once in a closed traversal. Result: An Euler circuit.
  3. Let your learner choose the steps for a new situation: Directed edges are A→B=4, A→C=2, C→B=1, B→D=3, C→D=7. Find a shortest A-to-D route. Ask which part of the model or rule carries over before checking the worked solution.
  4. After a short break, ask for an independent response: A connected undirected graph has six odd vertices. Can it have an Euler trail? Compare both the method and conclusion with the checkpoint answers, then revisit any misconception.

Ask and listen

  • A connected undirected graph has exactly two odd vertices P and Q. Where must an open Euler trail begin and end?
  • A route visits A,B,C,A,D using different edges. Does repeating A prevent it being a trail or being a path?

Adapt the practice

More support

Start with this prerequisite: Distinguish vertices from edges. Keep the visual visible. For the first guided problem, focus on this step: Every degree is even and the graph is connected, so all edges can be used once in a closed traversal.

More challenge

Try this application without looking at its answer: In a triangle A–B–C–A with a pendant edge A–D, does a Hamiltonian cycle through all four vertices exist? Then explain why the answer fits the stated domain or context.

Look for understanding

  • Your learner can complete this checkpoint and explain the method: A connected undirected graph has six odd vertices. Can it have an Euler trail?
  • Your learner can justify or challenge this statement/question using the mathematical definitions: A route visits A,B,C,A,D using different edges. Does repeating A prevent it being a trail or being a path?

Choose the next step

If either checkpoint needs prompting, repeat the worked model with changed values and revisit this caution: An Euler traversal concerns edges; a Hamiltonian traversal concerns vertices. When both are secure, use the linked Apply and extend resource and relevant VCE Key Knowledge/Key Skills activity.

Put the idea into practice

The matching topic collection includes learn-and-practise, application and checkpoint PDFs with worked answers. Download the free preview to see representative pages.

Explore this topic’s worksheets