QCE General Mathematics - Unit 4 - Graphs and networks
Planar Graphs, Paths and Cycles | QCE General Mathematics
Learn Euler's formula, walks, trails, paths, bridges, Eulerian and Hamiltonian routes for QCE General Mathematics.
Updated 2026-05-18 - 5 min read
QCAA official coverage - General Mathematics 2025 v1.3
Exact syllabus points covered
- Understand the meaning of planar graph and face.
- Apply Euler's formula to solve problems relating to planar graphs: $v+f-e=2$, where $v$ is number of vertices, $f$ is number of faces and $e$ is number of edges.
- Understand the meaning of walk, trail, path, open walk, open trail, open path, closed walk, closed trail (circuit), closed path (cycle), connected graph and bridge.
- Solve practical problems to determine the shortest path between two vertices in a weighted graph (by trial-and-error methods only).
- Understand the meaning of Eulerian trail, semi-Eulerian graph, Eulerian circuit and Eulerian graph, and the conditions for their existence.
- Solve practical problems involving semi-Eulerian graphs and Eulerian graphs.
- Understand the meaning of Hamiltonian path, semi-Hamiltonian graph, Hamiltonian cycle and Hamiltonian graph.
- Solve practical problems involving semi-Hamiltonian graphs and Hamiltonian graphs (by trial-and-error methods only).
Graphs can be redrawn without changing their connections. This matters for planar graphs, paths and cycles because the same network may look different while keeping the same mathematical structure.
Original Sylligence diagram for general euler path cycle.
Planar graphs and Euler's formula
A planar graph can be drawn so that edges meet only at vertices. The regions created are called faces. For connected planar graphs:
$ v+f-e=2 $
where $v$ is vertices, $f$ is faces and $e$ is edges.
Walks, trails and paths
| Term | Repeat edges? | Repeat vertices? | |---|---|---| | Walk | allowed | allowed | | Trail | not allowed | allowed | | Path | not allowed | not allowed | | Circuit | closed trail | start and end same | | Cycle | closed path | start and end same |
A bridge is an edge whose removal disconnects the graph.
Eulerian and Hamiltonian ideas
An Eulerian trail uses every edge exactly once. An Eulerian circuit starts and ends at the same vertex and uses every edge exactly once. A connected graph has an Eulerian circuit when every vertex has even degree. It has an Eulerian trail when exactly two vertices have odd degree.
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle returns to the starting vertex after visiting every vertex exactly once.
Worked example
Faces and redraws
The outside region of a planar drawing counts as a face. This is a common source of errors when using:
$ v+f-e=2 $
The same graph can often be redrawn in different planar-looking ways. Euler's formula depends on the graph structure, not the exact drawing style.
Connectedness and bridges
A connected graph has a route between every pair of vertices. A bridge is an edge whose removal disconnects the graph. Bridges matter in route problems because a bridge often forces a traveller to use that edge in a particular way.
Eulerian conditions
For a connected graph:
| Degree pattern | Result | |---|---| | all vertices even | Eulerian circuit exists | | exactly two vertices odd | Eulerian trail exists, starting and ending at the odd vertices | | more than two vertices odd | no Eulerian trail or circuit |
Hamiltonian questions do not have a simple degree shortcut at this level. Use trial and error and explain the route found, or explain why the required route is impossible if the graph structure forces a repeat.
Shortest path by trial
For small weighted graphs, list plausible routes and compare totals. The shortest route may pass through more vertices than a visually shorter-looking route if its edge weights are smaller.
Depth: walks, trails, paths and cycles
These words are not interchangeable.
| Term | Repeated vertices? | Repeated edges? | |---|---|---| | walk | allowed | allowed | | trail | allowed | not allowed | | path | not allowed | not allowed | | circuit | starts and ends at same vertex | usually no repeated edges | | cycle | starts and ends at same vertex | no repeated vertices except start/end |
Read the wording in a question carefully. A route that repeats a vertex may be valid as a walk but not as a path.
Eulerian ideas
An Eulerian trail uses every edge exactly once. An Eulerian circuit uses every edge exactly once and returns to the starting vertex.
For a connected graph:
| Degree pattern | Result | |---|---| | exactly 0 odd vertices | Eulerian circuit exists | | exactly 2 odd vertices | Eulerian trail exists but not an Eulerian circuit | | more than 2 odd vertices | no Eulerian trail using every edge once |
This is used in route-inspection style reasoning: if roads are edges, an Eulerian circuit means every road can be travelled once and the route can finish where it started.
Hamiltonian ideas
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to the start. Unlike Eulerian questions, Hamiltonian questions focus on vertices, not edges.
There is no simple degree test that works for every Hamiltonian graph in this course. Often the task is to inspect a diagram and decide whether such a path or cycle can be found.
Planar graphs and Euler's formula
For a connected planar graph:
$ v+f=e+2 $
where $v$ is vertices, $e$ is edges and $f$ is faces. The outside region counts as a face.
Depth: shortest path reasoning
Shortest path problems use edge weights such as distance, time or cost. A shortest path is not necessarily the path with the fewest edges. A route with more edges can be shorter if those edges have smaller weights.
A practical hand method is to label each vertex with the shortest confirmed distance from the start. Update neighbouring vertices only when a smaller total is found. Once the destination has the smallest temporary label, the shortest distance is confirmed.
When reporting the answer, give both the route and the total weight. A number alone does not show which path achieves it.