Networks and graph theory - Year 10 Mathematics

What you will learn

represent real situations as networks (graphs) with vertices and edges,
calculate the degree of each vertex and identify connected graphs,
apply Euler’s formula $F + V = E + 2$ to planar graphs,
determine whether an Eulerian path or circuit exists using vertex degrees,
solve practical problems involving transport, social networks, and wiring.

Worked example 0 Real-world example: bridge inspection

A council must inspect every bridge in a river district. The district has $5$ land masses connected by $8$ bridges. Can an inspector walk a route that crosses every bridge exactly once?

Model the land masses as vertices and bridges as edges.
Count the degree (number of edges) at each vertex.
An Eulerian path exists if there are exactly $0$ or $2$ vertices with odd degree.
If $2$ vertices have odd degree, the path must start at one and end at the other.
If all degrees are even, the inspector can complete an Eulerian circuit (returning to the start).

Key idea: the answer depends entirely on vertex degrees, not on the shape of the network.

1. What is a network?

A network (or graph) consists of vertices (also called nodes) connected by edges (also called arcs). Networks can model any situation involving objects and connections between them.

A simple network with 5 vertices (A to E) and 7 edges.

The degree of a vertex is the number of edges connected to it. In the graph above:

Vertex	Degree
A	3
B	3
C	2
D	2
E	4
Total	14

The sum of all degrees always equals twice the number of edges (here $2 \times 7 = 14$ ), because each edge contributes $1$ to the degree of each of its endpoints.

Handshaking lemma

$\sum \text{degrees} = 2 \times |\text{edges}|$

A graph is connected if you can travel from any vertex to any other vertex by following edges.

2. Euler’s formula for planar graphs

A planar graph can be drawn on a flat surface with no edges crossing. For any connected planar graph:

Euler's formula

Faces, vertices, edges

$F + V = E + 2$

where $F$ is the number of faces (regions, including the outer infinite region), $V$ is the number of vertices, and $E$ is the number of edges.

Worked example 1 Verifying Euler's formula

A planar graph has $V = 6$ vertices and $E = 9$ edges. How many faces does it have?

$F + V = E + 2$
$F + 6 = 9 + 2 = 11$
$F = 5$

The graph has $5$ faces (including the outer region).

3. Eulerian paths and circuits

An Eulerian path traverses every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

Condition	Result
All vertices have even degree	Eulerian circuit exists
Exactly $2$ vertices have odd degree	Eulerian path exists (start at one odd vertex, end at the other)
More than $2$ vertices have odd degree	Neither path nor circuit exists

Worked example 2 Checking traversability

For the network in the diagram above (vertices A to E), determine whether an Eulerian path or circuit exists.

Degrees: $A = 3$ , $B = 3$ , $C = 2$ , $D = 2$ , $E = 4$ .
Odd-degree vertices: $A$ and $B$ (two vertices).
Since exactly $2$ vertices have odd degree, an Eulerian path exists.
The path must start at $A$ and end at $B$ (or vice versa).
One such path: $A \to C \to E \to A \to B \to D \to E \to B$ .

4. Practical applications

Worked example 3 Minimum spanning tree thinking

Five towns are to be connected by roads. The costs (in thousands of dollars) for each possible road are shown below. What is the minimum total cost to connect all five towns?

Road	Cost
A—B	5
A—C	8
B—C	3
B—D	7
C—D	4
C—E	6
D—E	2

Start with the cheapest edge: $D$ — $E$ (cost $2$ ).
Next cheapest: $B$ — $C$ (cost $3$ ). No cycle formed.
Next: $C$ — $D$ (cost $4$ ). No cycle formed.
Next: $A$ — $B$ (cost $5$ ). No cycle formed.
All $5$ towns are now connected using $4$ edges. Total cost $= 2 + 3 + 4 + 5 = 14$ (thousands).

Key idea: a spanning tree connecting $n$ vertices always has exactly $n - 1$ edges.

Practice

Fluency

Tier 1: basic skills

A network has $4$ vertices with degrees $2, 3, 3, 4$ . How many edges does it have?
Draw a network with $4$ vertices where every vertex has degree $2$ .
A connected planar graph has $4$ vertices and $6$ edges. How many faces does it have?
A network has vertices with degrees $2, 2, 4, 4$ . Does an Eulerian circuit exist? Explain.
A network has vertices with degrees $1, 2, 2, 3$ . Does an Eulerian path exist? Explain.
True or false: a connected graph with $5$ vertices must have at least $4$ edges.
State Euler’s formula and define each variable.
A network has $8$ edges. What is the sum of all vertex degrees?

Reasoning

Tier 2: mixed practice

A connected planar graph has $5$ faces and $8$ edges. How many vertices does it have?
Draw a network representing the direct flights between four cities: Melbourne, Sydney, Brisbane, and Perth. Melbourne has direct flights to all three cities; Sydney and Brisbane are connected; Perth has no direct flight to Brisbane or Sydney. How many edges does your network have?
A postman must walk along every street in a neighbourhood. The network has vertex degrees: $2, 2, 2, 4, 4, 4$ . Can the postman complete an Eulerian circuit? Justify your answer.
A network has $6$ vertices and $10$ edges. Verify that it cannot be planar using the inequality $E \leq 3V - 6$ for simple planar graphs.
Three houses and three utilities (water, gas, electricity) must each be connected to every utility. Draw this as a bipartite network. How many edges are there? Is this graph planar?

Reasoning

Tier 3: explain and apply

A council wants to inspect every road in a town. The town’s network has $6$ intersections. Four intersections have degree $3$ and two have degree $4$ . Explain why an Eulerian path does not exist, and describe a strategy the council could use to inspect all roads.
Prove that in any network, the number of vertices with odd degree is always even. (Hint: use the handshaking lemma.)
A connected planar graph has $10$ vertices, each of degree $3$ . Find the number of edges and faces.
Explain the difference between a Hamiltonian path and an Eulerian path. Give an example of a graph that has an Eulerian circuit but no Hamiltonian circuit.

Challenge

Reasoning

Harder reasoning

The complete graph $K_5$ has $5$ vertices, each connected to every other vertex. Calculate the number of edges, the degree of each vertex, and determine whether an Eulerian circuit exists.
A network has $V$ vertices and is a tree (connected with no cycles). Prove that it has exactly $V - 1$ edges.
Seven bridges connect four land masses. The vertex degrees are $3, 3, 3, 5$ . Show that it is impossible to walk a route crossing each bridge exactly once. (This is the Konigsberg bridge problem.)
A delivery driver must visit $6$ locations. The distances (km) between each pair are given. The driver starts and ends at the depot (location A). Outline how you would use a network to find an efficient route, and explain why finding the absolute shortest route is computationally difficult for large networks.

Answers

Answer key

Attempt the practice first. When you're ready to check, expand the answers below.

Show the full answer key

Tier 1

Sum of degrees $= 2 + 3 + 3 + 4 = 12$ . Number of edges $= \dfrac{12}{2} = 6$ .
A square (cycle graph $C_4$ ): four vertices arranged in a loop, each connected to its two neighbours.
$F + V = E + 2$ , so $F + 4 = 6 + 2 = 8$ , giving $F = 4$ .
Yes. All vertex degrees ( $2, 2, 4, 4$ ) are even, so an Eulerian circuit exists.
Vertices with odd degree: the vertex with degree $1$ and the vertex with degree $3$ (two odd-degree vertices). So an Eulerian path exists (but not a circuit). It must start at one odd-degree vertex and end at the other.
True. A connected graph with $n$ vertices needs at least $n - 1$ edges (a spanning tree). For $n = 5$ , at least $4$ edges.
$F + V = E + 2$ , where $F$ = number of faces (regions), $V$ = number of vertices, $E$ = number of edges. Applies to connected planar graphs.
Sum of degrees $= 2 \times 8 = 16$ .

Tier 2

$F + V = E + 2$ , so $5 + V = 8 + 2 = 10$ , giving $V = 5$ .
Edges: Melbourne—Sydney, Melbourne—Brisbane, Melbourne—Perth, Sydney—Brisbane. Total $= 4$ edges.
Yes. All degrees ( $2, 2, 2, 4, 4, 4$ ) are even, so an Eulerian circuit exists. The postman can walk every street exactly once and return to the starting point.
For a simple planar graph: $E \leq 3V - 6$ . Here $3 \times 6 - 6 = 12$ and $E = 10 \leq 12$ , so this test alone does not prove non-planarity. In fact, a graph with $6$ vertices and $10$ edges could be planar. (The complete graph $K_4$ has $6$ edges; $K_5$ has $10$ edges and is not planar.) Since $K_5$ is the unique simple graph on $5$ vertices with $10$ edges, but we have $6$ vertices, a graph with $6$ vertices and $10$ edges may or may not be planar depending on its structure. The inequality is necessary but not sufficient.
Three houses and three utilities: each house connects to each utility, giving $3 \times 3 = 9$ edges. This is the complete bipartite graph $K_{3,3}$ , which is not planar (by Kuratowski’s theorem).

Tier 3

Four vertices have odd degree ( $3$ ). Since more than $2$ vertices have odd degree, no Eulerian path (or circuit) exists. Strategy: the council could identify pairs of odd-degree vertices and add duplicate edges (roads walked twice) to make all degrees even, minimising the total extra distance. This is the Chinese Postman approach.
The handshaking lemma states $\sum \text{degrees} = 2E$ . The left side is the sum of all degrees. Suppose $k$ vertices have odd degree. Each odd degree contributes an odd number to the sum, and each even degree contributes an even number. The total must be $2E$ (even). The sum of the even degrees is even. So the sum of the odd degrees must also be even, which requires $k$ to be even. Therefore the number of odd-degree vertices is always even.
Edges: sum of degrees $= 10 \times 3 = 30$ , so $E = \dfrac{30}{2} = 15$ . Faces: $F + V = E + 2$ , so $F + 10 = 15 + 2 = 17$ , giving $F = 7$ .
An Eulerian path visits every edge exactly once. A Hamiltonian path visits every vertex exactly once. Example: consider a graph shaped like a “bowtie” (two triangles sharing a single vertex). It has $5$ vertices and $6$ edges. The central vertex has degree $4$ and all others have degree $2$ — all even, so an Eulerian circuit exists. However, no Hamiltonian circuit exists because the graph is not $2$ -connected (removing the central vertex disconnects it).

Challenge

$K_5$ : each vertex connects to $4$ others, so each has degree $4$ . Number of edges $= \dbinom{5}{2} = 10$ . All degrees are even ( $4$ ), so an Eulerian circuit exists.
Base case: $V = 1$ , edges $= 0 = 1 - 1$ . Inductive step: a tree with $V > 1$ vertices has at least one leaf (vertex of degree $1$ ). Remove the leaf and its edge: the remaining graph is a connected tree with $V - 1$ vertices and (by hypothesis) $V - 2$ edges. Adding the leaf back gives $V - 1$ edges. So a tree on $V$ vertices has $V - 1$ edges.
The vertex degrees are $3, 3, 3, 5$ — all four are odd. Since there are $4$ odd-degree vertices (more than $2$ ), no Eulerian path or circuit exists. It is impossible to cross each bridge exactly once.
Model locations as vertices and distances as weighted edges. An efficient route visiting all locations and returning to the start is a Hamiltonian circuit. You can try nearest-neighbour or other heuristics. Finding the absolute shortest Hamiltonian circuit (the Travelling Salesman Problem) is computationally difficult because the number of possible routes grows factorially: for $n$ locations there are $\dfrac{(n-1)!}{2}$ distinct routes. For large $n$ , checking all routes is impractical, so heuristic or approximation methods are used.

Prefer paper? Print the answer key as a separate booklet: open print view ->