← All teaching guides
For the tutor · not Josh-facing

🚶 Euler, Hamiltonian + Critical Path

Unit 4 Topics 3 and 4 (journeys + scheduling half) · both of his "not sure where to start" flags live here · week 3 of the internal run
The concept in one sentence: Euler walks every LINE exactly once, Hamiltonian visits every DOT exactly once, and a critical path is the longest chain of waiting in a project, which is what sets the earliest possible finish.

The thing that makes it click: for the journeys, the mantra (edges vs vertices). For critical path, the dinner analogy: dinner is ready when the SLOWEST dish is ready, no matter how fast the salad was.

1 · Prerequisite check (30 seconds)

Degree of a vertex from a picture (he has it), and "odd or even?" on a handful of numbers. For critical path: can he read an activity table row as a sentence ("C takes 3 weeks and can't start until A is done")?

If the table-reading fails, that is the actual gap, not the maths. Practise translating rows to sentences before drawing anything.

2 · The teaching path

Journeys first (Euler → Hamiltonian):

  1. Concrete: the garbage truck (must drive every STREET) vs the sales rep (must visit every TOWN). Ask which is which before defining anything, he'll get it, and now the mantra is his idea
  2. The rule, discovered not told: draw three small graphs (all even; two odd; four odd). He tries to trace each without lifting the pen. Then count odd vertices together. The 0-or-2 rule lands as a discovery
  3. Notation: trail (different ends, exactly 2 odd) vs circuit (same ends, 0 odd). Trail must START and END at the odd pair, "the odd ones are the loose ends". QCAA's nouns, say them until they're old friends: a graph WITH an Euler trail is semi-Eulerian, with a circuit it's Eulerian; visit-every-vertex versions are semi-Hamiltonian (path) and Hamiltonian (cycle)

Critical path second (his teach-from-scratch flag, go slow):

  1. Concrete: making dinner. Lasagne 90 min, salad 10 min, table 5 min. When do we eat? Why doesn't hurrying the salad help? That IS float and the critical path, before any diagram
  2. Picture: the activity table → network drawn ACTIVITY-ON-ARC, the QCAA way: activities ride the ARROWS with their durations written on them, and the circles are just events (moments where arrows meet). He draws, you dictate rows as sentences. Boxes-with-durations-inside is a different convention and the exam's diagram won't look like it
  3. Entry method: list every start-to-finish path, add each up, LONGEST = minimum completion time. Path-listing is the concrete way in, the graphs are small enough
  4. Then the named method, because exam questions use these words: FORWARD scanning (left to right) gives every activity's EST, the earliest start time given what it waits for. BACKWARD scanning (right to left) gives the LST, the latest start that doesn't delay the finish. Float = LST − EST. Critical activities are the ones where float = 0. A question that says "use forward scanning" or asks for one activity's EST must be answerable in this vocabulary, path-listing alone can't do it
  5. Float with numbers: "E starts at week 7 because it waits for C. B finished at 5. So B could slip 2." Always a sentence with two numbers in it
Euler = every EDGE once (0 or 2 odd) · Hamiltonian = every VERTEX once (no rule, hunt) · critical path = LONGEST path
Streets or towns? Lines or dots?
Which dish is the lasagne here?

3 · Misconception catalogue (⭐ = seen in his diagnostic)

Looks likeWhy brains do itThe fix script
⭐ Critical path = shortest path"Critical" and "efficient" both sound like minimisingThe dinner table: "the SHORT path is the salad. Does dinner arrive when the salad's done?" Then: longest chain of waiting sets the finish
⭐ Mixes up which tool schedules a projectTool blur across the topicSame which-tool matching drill as week 2, now with critical path as a live option
Euler rule misremembered (thinks 1 odd vertex is fine)Rules memorised without the whyBack to pen-tracing: every time you pass THROUGH a vertex you use 2 of its edges, so odd degrees only survive at the two ends. 1 odd vertex is actually impossible (handshaking)
Hunts for a Hamiltonian degree ruleEuler had one, so this should too"Euler is the tidy twin. Hamiltonian you hunt by inspection, that's why exam graphs stay small"
Float = the activity's durationBoth are "time attached to a task""Float is the slack, not the size. How late can it run before anyone downstream notices?"
Justifies float with vibes ("B seems less important")Doesn't know a justification needs numbersThe two-number sentence frame: "___ starts at week ___, ___ finishes at week ___, so the float is ___"
Tries Euler's formula v + f − e = 2 on a trail questionTwo different things are named Euler, and one is printed in the book"Euler's FORMULA is about flat drawings and faces, and it lives in the book. The Euler TRAIL rule (0 or 2 odds) lives in your head." Name the collision before the exam does
Leaves float blank for a critical activity"There's nothing to calculate""Zero IS the answer, write it. Float = 0 is the finding, and saying it earns the mark"

4 · Questioning ladder

RungAskListen for
Recall"Euler trail needs how many odd vertices?""0 or 2", fast
DoThe park ranger (P, Q, R, S with 5 paths of 3 km): possible? route? distance?Counts degrees FIRST, finds odd pair Q and R, routes between them, 15 km
Explain back"Why must the walk start and end at the odd vertices?"Some version of "passing through uses edges in pairs, the odd ones are the loose ends"
TransferThe A6 B4 C3 D2 E2 activity table: minimum time, who can slip, by how muchLists paths (11 vs 8), names A-C-E critical, gives B and D 3 weeks WITH the two-number sentence

5 · How QCAA examines it

6 · Stuck scripts

Count the odd dots first. Then decide.
Lines or dots, which one does this question care about?
List every path start to finish. Add each one up. Which is the lasagne?
When can E actually start? When did B actually finish? The gap is the float.

7 · ADHD delivery notes