Networks and graph theory

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.