Distinguish walks, trails, paths, cycles, Eulerian trails and circuits, and Hamiltonian paths and cycles, and use the number of odd-degree vertices to decide whether an Eulerian trail or circuit exists in a connected graph

What this dot point is asking

VCAA wants you to describe ways of travelling through a graph and to apply the rules for Eulerian travel. You distinguish walks, trails, paths and cycles, recognise Eulerian trails and circuits (which use every edge once) and Hamiltonian paths and cycles (which visit every vertex once), and use the count of odd-degree vertices to decide whether an Eulerian trail or circuit exists. This is the traversal half of the Networks module, separate from optimisation.

The traversal vocabulary

• A walk is any sequence of edges, with repeats allowed.
• A trail is a walk that repeats no edge.
• A path is a walk that repeats no vertex (and so no edge).
• A cycle (or circuit) is a closed path that starts and ends at the same vertex.

These distinctions matter because the Eulerian and Hamiltonian conditions are stated in terms of them.

The odd-degree test for Eulerian travel

The degree of a vertex is the number of edges meeting it. The existence of Eulerian travel in a connected graph depends only on how many vertices have odd degree:

• Zero odd-degree vertices: an Eulerian circuit exists (and so does a trail). You can start anywhere and return to it.
• Exactly two odd-degree vertices: an Eulerian trail exists but not a circuit. You must start at one odd vertex and finish at the other.
• More than two odd-degree vertices: no Eulerian trail or circuit exists.

Hamiltonian paths and cycles

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does the same and returns to the start. Unlike the Eulerian case, there is no simple degree test, so in VCE you find one by inspection, listing a sequence of vertices that visits each once. The everyday example is a delivery van that must call at every house (vertex) once, regardless of which roads it uses.

The handshake result and why odd vertices come in pairs

Every edge contributes to the degree of exactly two vertices (its two endpoints), so the sum of all vertex degrees equals twice the number of edges and is therefore always even. It follows that the number of odd-degree vertices must itself be even, because the even-degree vertices contribute an even amount to the total and the odd ones must balance to keep the grand total even. This is why you never encounter exactly one or three odd-degree vertices, and why the Eulerian cases are zero or two odd vertices. Citing the handshake result is a clean way to justify, in a written-response question, why an inspection route with odd junctions cannot avoid repeated edges.

Making an Eulerian route possible by repeating edges

When a connected graph has more than two odd-degree vertices, no Eulerian trail or circuit exists, but a route that uses every edge at least once is still wanted in applications such as street sweeping or mail delivery. The fix is to repeat (duplicate) the smallest total weight of edges needed to make all but at most two vertices even. Each duplicated edge raises the degree of its two endpoints by one, so pairing up odd vertices with short connecting edges converts them to even. This is the intuition behind the Chinese postman idea: state which edges are repeated and add their weight to the total to give the shortest closed inspection route.

Choosing the start and finish for a trail

For a graph with exactly two odd-degree vertices, an Eulerian trail exists but a circuit does not, and the trail is forced to start at one odd vertex and finish at the other. The even-degree vertices can be passed through freely because each visit pairs an entering edge with a leaving edge, but at an odd vertex the edges cannot all be paired, which is why the route must begin or end there. When a question asks where an inspection must start, identify the two odd vertices and name them as the only valid endpoints. This single observation is often worth a mark on its own.

Why this matters for the exams

Eulerian questions are quick marks once you can count odd-degree vertices and state which kind of travel is possible and where it must start and end. Markers reward the correct count, the right conclusion, and naming the start and finish vertices for a trail. The Hamiltonian contrast is tested by asking you to write out a valid sequence of vertices, reinforcing the edge-versus-vertex distinction.