eduKate Singapore

VIEW THIS AS

Auto mode follows the Route Engine until you choose a viewpoint.

YOU ARE HERE

ROUTE CHECK

CONNECTED TO

WHAT NEXT

Use the canonical route for this room, or HELP if you are unsure.

Next useful routeCanonical hubHELP

Mathematics in Bukit Timah | Network Graphs, Euler Trails and Why Connections Matter

—

by

eduKate Asia
Original conceptual illustration of a connected six-node ring contrasted with two separated groups of three connected nodes; no labels or mathematical claims embedded in the cover.

Can someone draw a network of paths without lifting the pencil and without tracing the same connection twice? A pupil might try routes randomly, get stuck and assume the problem is impossible. Yet graph theory gives a remarkably simple test: count how many connections meet each junction. The number of odd-degree junctions often settles whether a complete edge-by-edge trail is possible before any route is attempted.

This Mathematics in Bukit Timah lesson uses a fictional network inspired by the idea of walking between green spaces, bridges and junctions. Every junction, crossing, connection, closure and network diagram below is invented for education. The lesson makes no claim about actual connections or access along the Rail Corridor, Bukit Timah Railway Station or neighbouring paths. A geometric drawing is not a pedestrian navigation map.

The quick rule is that a connected undirected network with at least one edge has an Euler circuit—a closed trail using every edge exactly once—if every vertex has even degree. It has an open Euler trail using every edge exactly once, beginning and ending at different vertices, if exactly two vertices have odd degree. A network with four odd-degree vertices cannot have such a complete trail.

Article contents

Original conceptual illustration comparing a connected cycle and two disconnected triangle networks, demonstrating that identical degrees do not imply identical connectivity; not an actual Bukit Timah map.

Quick answer: count connections, not distances

A graph consists of vertices, sometimes called nodes, and edges connecting them. A vertex may represent a junction; an edge may represent a path. Its degree is the number of incident edge ends, counting a loop twice if loops are permitted.

The mathematical goal in an Euler trail problem is to traverse each edge exactly once. Unlike a shortest-distance problem, this does not ask how many metres someone travels or how many different shortest paths exist.

The important assumptions are that connections are undirected and that all edges to be traversed lie in one connected component. If those conditions change, the simple Euler rules need a different interpretation.

Why the Bukit Timah connection is an imaginative setting

Bukit Timah’s green corridors and heritage railway landscape are familiar ways to picture junctions and paths. The image of crossing a bridge can prompt a counting puzzle.

But a real bridge is not automatically a graph-theoretic bridge, and not every drawn path is legally or safely accessible. The graph models relationships between abstract points, not actual current public access.

For real visits, consult authoritative site guidance and designated routes. The NParks Bukit Timah Nature Reserve information provides local context, not a validation of this article’s fictional network.

Draw vertices as dots and edges as connections

Begin with four imaginary junctions named A, B, C and D. Connect A–B, B–C, C–D and D–A. The drawing is a square cycle.

Every vertex has exactly two incident edges. It does not matter whether the square is drawn large, small, rotated or distorted, provided the connections remain unchanged.

Graph theory studies the connectivity structure. The straight-line lengths and drawing angles can change without changing the abstract graph.

Worked example 1: walk around a four-edge cycle

Our edges are AB, BC, CD and DA. Start at A, travel A→B→C→D→A, and stop.

Each edge is used once and the start and end vertex are the same. This is an Euler circuit.

A pupil can check the claim by crossing out each used edge in a list. Every edge appears exactly once; no extra edge remains unused. The repeated starting vertex is permitted because the restriction applies to edges, not to all vertices.

A walk, trail and simple path mean different things

A walk can repeat vertices and edges unless additional restrictions are supplied. A trail does not repeat edges, but it may revisit a vertex.

A simple path does not repeat vertices, apart from the special convention used when discussing simple cycles. An Euler trail is about edge coverage, not visiting every junction exactly once.

A learner who refuses to revisit any vertex may wrongly rule out valid Euler trails. Graph language matters because similar-looking routes have different rules.

What is degree?

The degree of a vertex is the number of incident edge ends. In the four-vertex cycle, each vertex has degree two.

If a new diagonal edge connects A and C, degrees become A=3, B=2, C=3 and D=2. The new edge increases the degree of both its endpoints by one.

The degree sequence 3,2,3,2 is enough to predict the possibility of an open Euler trail, once connectivity is checked.

Worked example 2: the square plus one diagonal

Take edges AB, BC, CD, DA and AC. Degrees of A and C are three, while B and D remain two. Exactly two vertices have odd degree.

One valid trail is A→B→C→D→A→C. It uses AB, BC, CD, DA and AC once each and ends at C rather than A.

This example demonstrates why the two odd-degree vertices must be the distinct starting and ending vertices in any Euler trail of this connected undirected graph.

Why odd vertices become endpoints

Imagine entering an internal junction along an unused edge and then leaving it along another unused edge. Those incident edges come in entry–exit pairs.

For a complete trail, every intermediate vertex needs an even number of used edge ends. A start may have one extra departure, and an end may have one extra arrival, so those two vertices may have odd degree.

That entry–exit argument explains the parity rule. It is not an arbitrary shortcut designed for one famous bridge puzzle.

Why a closed Euler circuit needs even degrees

In a closed trail, even the starting vertex has its departures paired with its returns. Every visit consumes two incident edge ends.

If all edges are to be covered and the route returns to its start, every vertex with edges must have even degree. Conversely, a connected undirected graph with every degree even has a closed Euler trail.

A proof of the converse involves following unused edges and splicing cycles when needed. Younger pupils can first understand the necessary pairing and test small connected graphs.

Worked example 3: four odd vertices block a complete trail

Return to the square with diagonal AC, then add a second diagonal BD. The graph has all four outer edges and both diagonals.

Every vertex now has degree three. Four vertices are odd, so no trail can use all six edges exactly once under the stated undirected graph.

This impossibility is a mathematical conclusion. Trying more random start points cannot overcome the parity obstruction.

A graph’s odd-degree count must be even

Every undirected edge contributes two to the sum of vertex degrees: one at each endpoint. A loop contributes two to one vertex under the standard convention.

Therefore the sum of degrees equals twice the number of edges. It is always even. Consequently, the number of vertices with odd degree must be even.

This is the handshaking lemma. It explains why a list of degrees containing exactly one or three odd entries cannot describe a finite undirected graph without a mistake in the supplied data.

Worked example 4: check edge and degree totals

In the square plus one diagonal, there are five edges. The degree sum is 3+2+3+2=10, which equals 2×5.

If a pupil’s degree table instead totals eleven, the graph has been misread or a connection was counted incorrectly.

This is a quick consistency check before applying the Euler theorem. It works even when the diagram is messy.

Connectedness is a separate requirement

Imagine six vertices forming two disconnected triangles, A–B–C–A and D–E–F–D. Every vertex has degree two.

Nevertheless, a single uninterrupted trail cannot traverse all six edges because there is no connection between the triangles. The even-degree condition alone does not establish a global Euler circuit.

The graph must be connected once isolated zero-degree vertices are disregarded. Degree and connectivity are distinct features.

Worked example 5: same degrees, different network

Network X is one six-vertex cycle. All six vertices have degree two, and the graph is connected, so it has an Euler circuit.

Network Y consists of two separate three-vertex cycles. Its six vertices also each have degree two, but the graph is disconnected and no one continuous route covers both components.

The two networks have the same degree sequence and different connectivity. A degree list cannot fully reconstruct the graph.

Why an isolated vertex is a special case

An isolated vertex has degree zero and no edges. If the task is to traverse every edge, it contributes nothing to be walked.

Many Euler-theorem statements therefore require that every vertex of nonzero degree lies in one connected component. An isolated dot elsewhere need not stop the edge-covering trail.

Students should read the exact convention used in a question. If instead the task requires visiting every vertex as well, an isolated vertex would matter in a different way.

A bridge in graph theory has a special definition

An edge is a bridge when removing it increases the number of connected components. A bridge can connect two parts of a network that otherwise have no alternative connection.

This is not synonymous with a physical bridge over water or road. A physical bridge on a loop might not be a graph-theoretic bridge, while a narrow abstract connection drawn as an ordinary line might be one.

The definition is about connectivity after deletion, not about materials or appearance.

Worked example 6: two triangles joined by one connection

Draw triangle A–B–C–A and triangle D–E–F–D, then connect C to D with a single additional edge CD.

Removing CD separates the network into two components. Hence CD is a graph-theoretic bridge.

The new degrees are C=3 and D=3; all other vertices have degree two. Exactly two odd-degree vertices occur, so an open Euler trail exists from C to D or vice versa.

An Euler trail can cross a bridge once

In the two-triangles example, begin at C, traverse the first triangle as C→A→B→C, cross bridge C→D, and traverse the second triangle as D→E→F→D.

Every edge is used once, and the route ends at D. It crosses the bridge only once.

If a pupil crosses CD too early and later tries to return to unfinished edges in the first triangle, the attempt can become stuck. This illustrates why the order of traversing unused connections matters even when a valid Euler trail exists.

A graph with a bridge cannot have an Euler circuit

Consider a connected graph whose edge e is a bridge. Removing e divides the connected part into two pieces.

A closed route that crosses from one piece to the other would need another connection to return without reusing e. By definition of a bridge, no alternative connection exists.

Thus a connected graph containing a bridge cannot have an Euler circuit covering all its edges. The two-triangle example permits an open trail, not a closed one.

The difference between possible and guaranteed from a chosen start

If a connected graph has exactly two odd-degree vertices, a complete open Euler trail exists, but it must start at one of those odd vertices and finish at the other.

Starting at an even-degree vertex does not yield a complete Euler trail across all edges in such a graph. A student should not conclude the graph is impossible just because one arbitrary start failed.

Checking the odd-degree endpoints before trying a route saves a great deal of trial and error.

Worked example 7: choose the proper starting vertex

The square plus AC has odd vertices A and C. The trail A→B→C→D→A→C is valid.

A proposed complete route starting at B and ending at D cannot be an Euler trail, because B and D have even degree and the graph has distinct odd endpoints A and C.

There is no need to enumerate every possible route from B to prove the claim. Degree parity settles it.

Traversing every edge differs from visiting every vertex

A route visiting each vertex exactly once is associated with Hamiltonian paths, not Euler trails. The two problems have different conditions and no simple identical test.

A network may have an Euler circuit that revisits junctions, while a simple Hamiltonian cycle uses each vertex once before returning to its start. Confusing the terms can produce an answer to the wrong problem.

The lesson does not require solving arbitrary Hamiltonian problems. It requires understanding what is being counted as a repeat.

Worked example 8: a revisited vertex can be allowed

Return to trail A→B→C→D→A→C on the square plus diagonal. The vertex A appears twice in the written route and C appears at an intermediate position and the endpoint.

No edge repeats. Therefore the route is a valid Euler trail despite repeated vertices.

A learner who calls it invalid purely because A reappears has applied a simple-path restriction that the Euler question never gave.

What if the network has directed arrows?

An undirected edge can be traversed in either direction. A directed graph has arcs with specified directions, and a valid route must follow those arrows.

The undirected odd-degree rule cannot simply be applied to directed networks. Directed Euler conditions use incoming and outgoing degrees together with suitable connectivity assumptions.

A classroom should state whether connections are one-way or two-way before counting. An arrow on a diagram is mathematical data, not decoration.

Worked example 9: a directed three-cycle

Imagine directed arcs A→B, B→C and C→A. Each vertex has one incoming and one outgoing arc.

The directed route A→B→C→A traverses every arc exactly once and returns to A.

The total undirected degree of each vertex would be two, but for directed graphs the useful balance is indegree=outdegree at each vertex. This example shows the relevant distinction without implying real one-way streets.

A degree list does not tell the route order

Even if a connected graph satisfies the Euler condition, the degree table does not specify a particular full trail. Several different Euler trails or circuits may exist.

The theorem answers existence under given conditions. Constructing a trail requires an additional procedure, whether guided inspection or a systematic graph algorithm.

Distinguish “prove a route exists” from “write one actual sequence.” An existence statement alone does not fulfil a question demanding a route list.

A practical pencil algorithm can work for small graphs

For a small connected graph, identify odd-degree vertices first. Start at one of them if two are odd; otherwise start at any vertex with incident edges.

Follow unused edges while trying not to cut off all remaining unused work. Cross out an edge once traversed and check whether you have stranded unused edges behind a bridge-like remaining connection.

This is a classroom heuristic inspired by Euler-trail construction. Formal algorithms such as Hierholzer’s method provide a systematic way to build circuits and splice unused cycles.

Worked example 10: find a route by checking every edge

Take edges AB, BC, CD, DA, AC again. Begin at A. Use AB, then BC, then CD, then DA, then AC.

The visited vertex sequence is A,B,C,D,A,C. Compare the used edge list with the original: every one of the five appears once.

A completed answer should list the route and provide a coverage check. Without checking, it is easy to miss a small diagonal that remains unused.

When removing an edge changes degree parity

An undirected nonloop edge has two endpoints. Removing it reduces each endpoint degree by one, flipping each endpoint’s parity.

In the four-vertex graph containing all square edges and both diagonals, every degree is three. Remove diagonal BD, and degrees at B and D become two while A and C remain three.

The new graph has exactly two odd vertices and becomes eligible for an open Euler trail. This is a precise way to diagnose what minimal changes might achieve a desired trail condition.

Worked example 11: repair an impossible network

Initially the square with diagonals AC and BD has four odd vertices and no Euler trail. Remove BD.

The remaining five edges produce degrees 3,2,3,2 at A,B,C,D. The graph stays connected and now permits the route A→B→C→D→A→C.

This repair removes one connection rather than asking pupils to repeatedly force an impossible traversal. Changing the graph changes the mathematical answer.

Pairing odd vertices with new edges

A connected undirected graph has an even number of odd-degree vertices. Adding an edge between two odd vertices makes both degrees even, potentially reducing the odd count by two.

For a graph with exactly four odd-degree vertices, adding suitable connections between paired odd vertices may produce an Euler circuit, provided the graph remains appropriately connected and parallel edges are allowed where needed.

This is an advanced design extension. Real infrastructure cannot be altered merely because a graph would have nicer parity.

The classic seven-bridges idea is a mathematical history lesson

Euler’s historical Königsberg bridges problem motivated early graph-theoretic reasoning about using each bridge exactly once. The key move was to ignore irrelevant geographic distances and count the land regions and their connections.

This historical example is conceptually separate from any actual Bukit Timah bridges. Our invented networks illustrate the same abstract edge-traversal question without pretending to reproduce Königsberg’s historical map.

The transfer lesson is abstraction: retain the connections that control the question and discard drawing details that do not.

Connected components tell us which route questions are impossible

A connected component is a maximal set of vertices linked by walks through the graph. Separate components have no edge path connecting them.

If all required edges are spread across two different components, a single uninterrupted edge trail cannot cover both without an added connection or a separate journey.

Counting components therefore comes before applying an Euler existence test. Students can circle components on a drawing to see the obstruction directly.

Worked example 12: an isolated square and triangle

Imagine edges AB,BC,CD,DA forming a square and edges EF,FG,GE forming a separate triangle. Every vertex in each component has degree two.

The complete seven-edge graph has two edge-bearing components. No one continuous Euler trail covers all seven edges.

Each component separately has an Euler circuit. This is why saying “all degrees even” without checking connectivity is incomplete.

A connected graph can have multiple valid tours

In a symmetric network with several cycles sharing vertices, multiple orders may traverse all edges without repeats. The Euler theorem predicts possibility, not a unique route.

For example, a small figure-eight of two triangles sharing one vertex has all degrees even: the shared vertex has degree four and the others degree two. One can traverse one triangle first or the other first and return to the shared vertex.

The start point may be chosen differently for a circuit, subject to valid connections. This flexibility is useful in puzzles but should not be confused with a claim about one uniquely shortest route.

An Euler circuit does not necessarily minimise travel distance

If a connected graph admits an Euler circuit, it uses each edge once, so its total traversed edge length equals the sum of edge lengths. However, if no Euler circuit exists and repeated edges are allowed, finding a shortest closed edge-covering walk is a different optimisation problem.

That more advanced problem is related to route inspection or the Chinese postman problem. It may require choosing which edges to repeat.

The phrase “Euler trail” alone should not be used to promise a shortest delivery or inspection route in an arbitrary weighted network.

A weighted graph adds distances or costs

Edges can be labelled with lengths, times or fictional effort units. Their labels become relevant to shortest-path or minimum-cost problems, although the pure Euler existence rule still depends on connectivity and degree parity.

For a classroom example, a route using every edge exactly once has total edge length equal to the sum of all edge labels, regardless of traversal order.

A model of a real walking trail would need verified distances and access restrictions. Here edge weights are hypothetical and serve only a mathematical purpose.

Worked example 13: a weighted Euler trail

Suppose the five edges AB,BC,CD,DA,AC have fictional lengths 2,3,4,5 and 6 units respectively.

The Euler trail A→B→C→D→A→C uses all five once, so its total is 2+3+4+5+6=20 units.

This does not mean the route has twenty metres or takes twenty minutes unless the problem has supplied a valid unit or rate. The degree theorem and the weight sum answer distinct questions.

Counting handshakes is another graph-theory application

Imagine five fictional people where an edge represents a single mutual handshake between two different people. Each person’s degree counts how many other people they shook hands with.

The handshaking lemma says the sum of all five handshake counts equals twice the number of distinct handshakes, because each handshake has two participants.

This works for an undirected simple graph and prevents double-counting. It does not assert that everyone in an actual class has shaken hands or that any real survey took place.

Worked example 14: degree sum from a fictional class

Suppose five imaginary pupils have handshake degrees 2,2,2,1 and 1. The sum is eight.

If those degrees come from a valid simple undirected handshake graph, there are 8/2=4 handshakes. Two of the pupils have odd degree, consistent with the general parity rule.

Degree sums are a rapid audit. They can also show that a proposed list containing an odd total is impossible for any undirected graph.

Same number of vertices does not mean same connectivity

Two networks may have four vertices each but very different numbers of edges and components. A completely disconnected set of four dots has no edges, while a complete four-vertex graph has all six possible distinct pair connections.

A student’s diagram must therefore specify edges explicitly. Merely knowing the names of four junctions cannot determine whether any route exists.

This is why graph problems often begin with an edge list, adjacency table or drawing rather than only a count of places.

Geometry on the page does not always create a junction

Two lines drawn crossing each other are not necessarily joined in an abstract graph. Unless a vertex is marked or the problem states that the crossing is a connection, one line may conceptually pass over the other.

Conversely, an edge can curve around another edge without changing which vertices it connects.

For educational route modelling, make every junction explicit. Assuming all visual crossings are usable links may alter degrees and the Euler answer.

What a tutor should diagnose when a trail fails

A child may confuse edges with vertices, forbid all vertex revisits, miscount a diagonal, ignore disconnected components or choose a start that is not an odd-degree vertex.

Each error needs a different repair. Have the learner first list all edges, then compute degrees, confirm connectivity and finally attempt an Euler trail.

A short error log recording the first incorrect assumption is often more useful than giving a fresh complicated network immediately.

Primary progression: draw simple routes and count ends

Younger Primary students can trace triangles and squares, count how many edges touch each dot and check whether a pencil route has repeated an edge.

Use tiny graphs of three or four vertices. Formal Euler language can follow once students understand the distinction between a point and a connection.

The learning goal is systematic checking, not an expectation that Primary pupils must master graph algorithms.

Lower Secondary progression: parity and explanations

Students comfortable with odd and even numbers can study degrees, verify the handshaking lemma and test the Euler circuit and trail conditions on connected undirected examples.

Ask for a reason why two odd vertices allow a different start and end. The entry–exit pairing provides a conceptual explanation.

This connects familiar number parity to a new visual structure and makes a route puzzle into generalisable Mathematics.

Upper-level extension: algorithmic networks

Learners ready for advanced reasoning can compare Euler problems with Hamiltonian problems, explore directed graphs and implement a simple trail-finding algorithm.

The enrichment should be labelled as such. Not every Singapore school examination includes graph theory or algorithm design at the level discussed here.

The broader purpose is to see why definitions and constraints must be checked before applying a theorem.

A twenty-minute home diagnostic

Minutes 1–5: Draw a square cycle A–B–C–D–A. Ask for each degree. Answer: every degree is two.

Minutes 6–10: Add diagonal AC. Find degrees A=3,C=3,B=2,D=2. Predict that an open Euler trail is possible.

Minutes 11–15: Write A→B→C→D→A→C and cross off every edge used once. Explain why revisiting vertex A is permitted.

Minutes 16–20: Add diagonal BD as well. All four vertices become odd, so a complete Euler trail becomes impossible. Ask the student to explain the parity obstruction rather than simply try more routes.

A seven-day practice sequence

Day one identifies vertices and edges. Day two counts degrees. Day three checks sums of degrees against twice the edge count. Day four distinguishes walks, trails and simple paths.

Day five tests Euler circuits and two-odd-vertex trails. Day six adds disconnected components and graph-theoretic bridges. Day seven changes one edge in a fresh network and asks whether the conclusion survives.

If the learner cannot count edges accurately, repair that prerequisite before introducing more elaborate algorithms.

Five challenge questions with answers

A. A connected four-edge square cycle has degree two at every vertex. Euler circuit? Answer: yes.

B. A connected square plus one diagonal has exactly two odd-degree vertices. Euler trail? Answer: yes, from one odd vertex to the other.

C. A connected four-vertex graph has every vertex of degree three. Euler trail? Answer: no, because four vertices have odd degree.

D. Two disconnected triangles have even degrees at every vertex. One continuous Euler circuit covering all edges? Answer: no; the edge-bearing graph is disconnected.

E. A graph has seven edges. What must its degree sum be? Answer: fourteen, under the standard undirected degree convention.

Frequently asked questions

Does an Euler trail use each vertex exactly once?

No. It uses each edge exactly once. Vertices can be revisited.

Can a network have an Euler circuit with two odd-degree vertices?

No. For a connected undirected graph with edges, a closed Euler circuit requires every vertex to have even degree.

Can a network with two odd vertices have a trail from any start?

A full open Euler trail must begin at one odd-degree vertex and finish at the other.

Does a graph-theoretic bridge have to be a physical bridge?

No. It is any edge whose deletion increases the number of connected components.

Why must the graph be connected?

A single uninterrupted trail cannot cover edges lying in separate components without a connecting edge.

Are these actual Bukit Timah walking paths?

No. The diagrams and connections are imaginary educational graphs, not route maps.

Is an Euler route always a shortest route?

Not automatically. Euler existence concerns using every edge once. General shortest-route optimisation is a separate problem.

Is graph theory part of every Secondary Mathematics exam?

No. This is an enrichment application of parity, logical reasoning and networks; check the student’s actual syllabus.

How can parents tell if the concept is understood?

The learner can identify what repeats are prohibited, count vertex degrees, test connectivity and justify a complete edge list instead of simply guessing a route.

Official curriculum context and the next mathematics connection

For school-level foundations, consult the MOE Primary Mathematics syllabus and the SEAB 2027 G3 Mathematics syllabus directory. The graph-theory theorems in this lesson are mathematical enrichment rather than a claim of universal examination coverage.

For a different counting objective, see Mathematics in Bukit Timah | Counting Grid Paths with Pascal’s Triangle. For geometric distances along an imaginary map, read Coordinate Distance and Perpendicular Bisectors. The immutable Clementi Secondary 1 Mathematics small-group reference anchors the series’ emphasis on definitions, worked checks, diagnosis and independent reasoning.

The durable habit is to name what must be traversed, check how vertices and edges connect, use parity to test possibility, then verify the proposed trail edge by edge. That is the mathematical skill behind a network puzzle, regardless of where its fictional junctions are drawn.

Read the other three Mathematics in Bukit Timah articles in this batch: Modular arithmetic, number codes and check digits · Functions, inverses and restricted domains · Bisection, numerical methods and square roots. These four guides use different mathematical concepts, fictional teaching data and explicit limits on what each model proves.

Discover more from eduKate Singapore

Subscribe now to keep reading and get access to the full archive.

Continue reading