BTT Mathematics / Primary Mathematics Learning Hub / Route Networks

Primary Mathematics: Route Networks, Euler Trails and Traversal Puzzles | Worked Learning Guide

A route puzzle becomes easier when the drawing is reduced to what matters: places to enter or leave, and connections that may or may not be used.

This guide is Primary Mathematics enrichment. It introduces networks, vertices, edges, route tracing, one-stroke drawings, bridge-style puzzles, Euler trails, Euler circuits, degree counting, route impossibility and systematic verification. The aim is not formal graph theory terminology for its own sake. The aim is to turn messy route pictures into countable structure.

Wait, What? A Map Can Be Simplified Without Changing the Route Problem

Suppose four rooms are connected by corridors. The physical shape of each room is irrelevant if the question asks whether every corridor can be walked exactly once. Replace each room by a point and each corridor by a line. The simplified network keeps the connectivity while removing decoration.

1. Vertices and Edges

A vertex is a point where routes meet or terminate. An edge is a connection between two vertices.

In a road network, junctions can be vertices and roads can be edges. In a bridge puzzle, land regions can be vertices and bridges can be edges.

Worked Example 1: Count the Structure

A triangle has three corners and three sides.

Network view: 3 vertices, 3 edges.

Worked Example 2: Add a Diagonal

A square has four sides and one diagonal.

Vertices = 4. Edges = 5.

2. Degree: How Many Edges Meet a Vertex?

The degree of a vertex is the number of incident edges. A dead end has degree 1. A simple bend or pass-through junction may have degree 2. A three-way junction has degree 3.

Worked Example 3: Degrees in a Path

For A—B—C—D, degrees are 1,2,2,1.

The two endpoints have odd degree; the middle points have even degree.

Worked Example 4: Degrees in a Cycle

For a square cycle A—B—C—D—A, every vertex has degree 2.

3. One-Stroke Drawings

A one-stroke drawing uses every edge exactly once without lifting the pencil. Vertices may be visited more than once. The condition applies to edges, not vertices.

Worked Example 5: Simple Path

A—B—C—D can be drawn in one stroke starting at A and ending at D.

Worked Example 6: Simple Cycle

A square can be drawn in one stroke and return to the starting point because every vertex has even degree.

4. Why Odd-Degree Vertices Matter

When a route enters a middle vertex along an unused edge, it usually needs another unused edge to leave. Edges at an internal visit therefore pair up: enter, leave; enter, leave. That pairing makes even degree natural for vertices used only internally.

A start can have one unpaired leaving edge. An end can have one unpaired entering edge. Therefore a one-stroke route that does not return to its start can have exactly two odd-degree vertices: the start and the end.

Worked Example 7: Exactly Two Odd Vertices

A network has vertex degrees 1,2,2,1.

Exactly two vertices are odd, so a one-stroke route is possible if the network is connected, beginning at one odd vertex and ending at the other.

Worked Example 8: Zero Odd Vertices

A cycle has all degrees even. A one-stroke route can start anywhere and return to the start.

5. When One-Stroke Traversal Is Impossible

If a connected network has more than two odd-degree vertices, using every edge exactly once in one continuous trail is impossible.

Worked Example 9: Four Odd Vertices

A plus-shaped network has one centre connected to four endpoints. The centre has degree 4; each endpoint degree 1. There are four odd vertices.

No one-stroke trail can use every edge exactly once.

Worked Example 10: Why the Failure Occurs

Each of the four degree-1 endpoints demands to be a start or end because once entered there is no unused route to leave. But a single trail has only one start and one end. Four endpoint demands cannot fit into two positions.

6. Connectivity Comes First

Even if every vertex has even degree, disconnected pieces cannot be covered by one continuous route without lifting the pencil or using a nonexistent edge.

Worked Example 11: Two Separate Squares

Each square individually has all even degrees, but the two squares are disconnected. There is no single trail covering both without lifting the pencil.

7. Euler Trails and Euler Circuits

An Euler trail uses every edge exactly once. An Euler circuit is an Euler trail that ends where it started.

• Connected + 0 odd vertices → Euler circuit exists.
• Connected + 2 odd vertices → Euler trail exists, starting and ending at the odd vertices.
• Connected + more than 2 odd vertices → no Euler trail.

8. Route Construction: Existence Is Not the Same as Finding the Route

Knowing a trail exists does not automatically produce it. A learner must choose edges so that unused parts do not become trapped behind a closed section too early.

Worked Example 12: Avoid Premature Closure

In a network with a large loop and a side loop attached at one vertex, completing the large loop and returning to the attachment point before using the side loop can still work if unused edges remain accessible there. But closing a section that isolates unused edges elsewhere can fail.

A practical Primary strategy is: when possible, avoid using a bridge-like edge that disconnects remaining unused edges until necessary.

9. Bridges in a Network

An edge is a bridge if removing it disconnects the network into separate parts. In route puzzles, bridges often control when a region must be entered or left.

Worked Example 13: Single Connection Between Two Clusters

Two loops are connected by one edge. That connecting edge is a bridge. If a trail crosses it, the route changes from one cluster to the other. Whether it can return depends on whether another connection exists.

10. Counting by the Handshaking Idea

Every edge touches two endpoints. Therefore the sum of all vertex degrees equals twice the number of edges.

Degree sum = 2 × number of edges.

Worked Example 14: Check an Edge Count

Degrees are 3,3,2,2.

Degree sum = 10, so edges = 10 ÷ 2 = 5.

Worked Example 15: Reject Impossible Degree Data

Someone claims a network has degrees 3,2,2,2.

Degree sum = 9, but degree sum must be even because it equals twice the edge count. Therefore the data cannot describe an ordinary undirected network.

11. Odd Vertices Must Come in an Even Number

Because the degree sum is even, the number of odd-degree vertices must be even. One odd-degree vertex by itself is impossible; three odd-degree vertices are impossible.

Worked Example 16: Missing Degree Parity

Four known degrees are 2,3,4,5 and one unknown degree x. The known odd degrees are 3 and 5, already two. If the whole network is ordinary and connected, x may be even or may create two more odds only if another unknown exists. With just one unknown, x must be even to keep an even number of odd vertices.

12. Shortest Route Versus Edge-Once Route

These are different problems. A shortest-path question may ignore many edges. An Euler-trail question must use every edge exactly once. Do not use the wrong objective.

Worked Example 17: Shortest Path

From A to D, routes have lengths 3, 5 and 6 edges. The shortest path uses 3.

This says nothing about whether every edge in the network can be traversed exactly once.

13. Repeating Edges When One-Stroke Is Impossible

If a route inspector must cover every edge and return to the start, but odd vertices exist, some edges may need to be repeated. The enrichment question becomes: which repetitions pair odd vertices most efficiently?

Worked Example 18: Simple Path Return

A—B—C has two edges. To start at A, cover every edge and return to A, travel A-B-C-B-A. Each edge is used twice.

The original network has odd endpoints A and C, so a closed edge-once route is impossible.

14. Grid Networks

Grid drawings can be simplified into vertices and unit edges. Interior grid points usually have degree 4, corner points degree 2, and edge points degree 3 depending on the drawn boundaries.

Worked Example 19: 1×1 Square

Four corner vertices, each degree 2. Euler circuit exists.

Worked Example 20: Two Adjacent Squares

There are six corner/junction vertices. The two shared-middle vertices have degree 3; the four outside corner vertices have degree 2. Exactly two odd vertices, so an Euler trail exists starting at one degree-3 vertex and ending at the other.

15. Route Puzzles With Rules

Some puzzles add directions, forbidden edges, one-way paths or required start/end points. The Euler parity test still helps, but only after the allowed network has been defined correctly.

Worked Example 21: Required Start Point

A connected network has exactly two odd vertices X and Y. If the puzzle requires a one-stroke route starting at even-degree vertex Z, no solution exists because an open Euler trail must start at X or Y.

Worked Example 22: Required Closed Route

A connected network has exactly two odd vertices. An Euler trail exists, but an Euler circuit does not. If the task requires returning to the starting point without repeating edges, the answer is impossible.

16. Common Errors

• Counting vertices instead of edges when the question asks for route segments.
• Assuming a one-stroke drawing cannot revisit a vertex.
• Ignoring disconnected components.
• Checking odd-degree count but not the required start/end point.
• Confusing shortest path with edge-once traversal.
• Counting a crossing as a vertex when the lines merely cross without connection.
• Forgetting that each edge contributes two to the total degree sum.
• Claiming a one-stroke route exists with four odd vertices.

17. Error Repair

Error A: “Four odd vertices is fine because four is even.”

The number of odd vertices must indeed be even, but an Euler trail needs specifically zero or two odd vertices. Four is compatible with a network but not with a one-stroke edge-once trail.

Error B: “A vertex may be visited only once.”

False. Edges are the objects that must be used exactly once. Vertices may be revisited.

Error C: “All degrees even means a trail exists.”

Only if the relevant network is connected. Separate components still require a lift or nonexistent connection.

18. Practice: 24 Original Questions

Questions 1–8: Structure and Degree

1. How many vertices and edges does a triangle have?
2. How many vertices and edges does a square with one diagonal have?
3. Find the degrees in A—B—C—D.
4. Find the degrees of the four vertices of a square cycle.
5. A plus-shaped network has a centre joined to four endpoints. Find all degrees.
6. Degrees are 3,3,2,2. Find the number of edges.
7. Explain why degrees 3,2,2,2 cannot form an ordinary undirected network.
8. Can a network have exactly one odd-degree vertex? Explain.

Questions 9–16: One-Stroke Traversal

9. Can A—B—C—D be drawn in one stroke using every edge once? State start and end.
10. Can a square cycle be drawn in one stroke and return to the start?
11. Can the plus-shaped network in Question 5 be drawn in one stroke using every edge once?
12. Two separate squares are disconnected. Can one continuous edge-once trail cover both?
13. A connected network has 0 odd vertices. What type of Euler route exists?
14. A connected network has exactly 2 odd vertices X and Y. Where must an open Euler trail start and end?
15. A connected network has 6 odd vertices. Can an Euler trail exist?
16. A connected network has exactly two odd vertices but the required starting point is an even vertex. Can an edge-once trail satisfy that requirement?

Questions 17–24: Transfer

17. Two adjacent squares share one side. How many vertices have odd degree?
18. Does the two-adjacent-squares network have an Euler trail?
19. Does it have an Euler circuit?
20. A network has degree sum 18. How many edges does it have?
21. A connected network has all even degrees. What must be true about a one-stroke route?
22. A connected network has four odd vertices. What is the minimum number of separate trails needed to cover all edges without repeating, in a simple decomposition?
23. A path A—B—C must be covered starting and ending at A. Which edges must be repeated?
24. Explain in one paragraph why odd vertices control the possible start and end of an Euler trail.

19. Worked Answers

1. 3 vertices, 3 edges. 2. 4 vertices, 5 edges. 3. 1,2,2,1. 4. All 2. 5. Centre 4; four endpoints 1 each. 6. 5 edges. 7. Degree sum is 9, but it must be even. 8. No; odd vertices occur in even number.

9. Yes, start A end D or reverse. 10. Yes, Euler circuit. 11. No, four odd vertices. 12. No, disconnected. 13. Euler circuit. 14. Start X and end Y, or reverse. 15. No. 16. No; an open Euler trail must start at one odd vertex.

17. Two odd vertices: the two shared-side endpoints have degree 3. 18. Yes. 19. No, because two odd vertices prevent a circuit. 20. 9 edges. 21. A closed Euler circuit exists. 22. At least 2 trails are needed to pair four odd endpoints in a simple decomposition. 23. A-B and B-C must each be traversed twice in route A-B-C-B-A. 24. At internal visits, unused incident edges pair as enter/leave. Only the start and end may have one unpaired incident edge, so they are the two odd vertices.

20. Checking Ladder

• Have I identified the correct vertices and edges?
• Are crossings actual junctions?
• Is the network connected?
• How many vertices have odd degree?
• Does the requested start/end condition match the odd vertices?
• Is the task shortest path, edge-once trail or closed traversal?
• Does the degree sum equal twice the edge count?

21. Transfer Test

Draw a 2×2 square grid. Count the degree of each vertex, determine the number of odd vertices and decide whether every edge can be traced exactly once in one stroke. If not, identify the minimum structural change—such as adding or removing one edge—that could change the parity condition, and justify your proposal.

22. Delayed Return

Three days later, take four unfamiliar line drawings. Reduce each to a network, list vertex degrees and classify it as Euler circuit possible, Euler trail only, impossible in one trail, or disconnected.

23. Parent and Tutor Guide

Do not begin with terminology. Give the learner a route drawing and ask, “Where can you enter and leave? Which connections have to be used?” After the child experiences why endpoints and junctions matter, introduce degree as a counting tool. Let parity explain the puzzle rather than become another rule to memorise.

24. Mastery Receipt

• I simplify route drawings into vertices and edges.
• I calculate vertex degrees.
• I know that degree sum equals twice the edge count.
• I recognise that odd vertices occur in even number.
• I distinguish Euler trails from Euler circuits.
• I check connectivity before applying parity rules.
• I distinguish edge-once traversal from shortest-path problems.
• I can justify why zero or two odd vertices are special.

Official Reference Route

Singapore Ministry of Education — Primary Mathematics Syllabus P1–P6, updated October 2025

This is enrichment content; formal graph theory is not claimed as a universal Primary requirement.

Continue the Next Enrichment Batch

• BTT Primary Mathematics Learning Hub
• Sets, Venn Diagrams and Inclusion–Exclusion
• Matchstick Patterns, Figurate Numbers and Visual Sequences
• Number Bases, Place-Value Codes and Numeral Systems

The Quiet Return

A route puzzle becomes mathematical when the learner stops following the drawing by eye and starts counting what every junction requires. Parity turns wandering into proof.