# Networks, Paths and Circuits

> Vertices, edges and degrees, planar and isomorphic graphs, Euler trails and circuits, Hamiltonian paths and shortest paths.

From HSC Maths Advanced on WhizzNotes, free study notes for NSW students: https://whizznotes.com/mathematics-advanced/networks/. Updated 3 November 2026.
Year 11 and Year 12 boxes go deeper than the Year 10 text around them.

### Story time: The bridges of Königsberg
In the 1700s, the city of Königsberg had seven bridges joining four areas of land. People wondered: can you walk around the city crossing every bridge exactly once? Nobody could do it, but nobody could prove it was impossible.

The mathematician Leonhard Euler turned the map into dots (land) and lines (bridges). By counting how many lines met at each dot, he proved the walk is impossible. That picture was the first **network**. Today networks plan delivery routes, internet traffic and train lines.

**In short:** A network is a set of points (vertices) joined by lines (edges), like a map of towns and roads. An Euler trail uses every edge once and needs 0 or 2 odd vertices, a Hamiltonian path visits every vertex once, and the shortest path has the smallest total weight.

## Starting point: Years 9 and 10

### Network words

- A **network** (or graph) is a set of **vertices** (dots) joined by **edges** (lines).
- The **degree** of a vertex is the number of edges that meet there. A loop counts twice.
- A **directed** network has arrows: edges go one way. A **weighted** network has numbers on its edges, such as distances or costs.
- A network is **connected** if you can get from any vertex to any other.

### Key idea: Sum of degrees
Every edge has two ends, so

$$\text{sum of all degrees} = 2 \times \text{number of edges}$$

This means the number of odd-degree vertices is always even.

### Walks, trails, paths and circuits

- **Walk:** any route along edges.
- **Trail:** a walk with no repeated edges.
- **Path:** a walk with no repeated vertices (so no repeated edges either).
- **Circuit:** a trail that starts and ends at the same vertex. **Cycle:** a path that does this.

### Euler trails and circuits

An **Euler trail** uses every edge exactly once. An **Euler circuit** does this and returns to the start.

### Key idea: Euler's rule for a connected network
- **0 odd vertices:** an Euler circuit exists.
- **2 odd vertices:** an Euler trail exists. It must start at one odd vertex and end at the other.
- **More than 2 odd vertices:** neither exists.

The Königsberg network has four vertices, all of odd degree, so no walk crosses every bridge once.

### Hamiltonian paths and cycles

A **Hamiltonian path** visits every **vertex** exactly once. A **Hamiltonian cycle** also returns to the start. There is no simple rule for these, so you test by trying routes.

### Watch out: Edges or vertices?
Euler is about **edges** (every road once, like a street sweeper). Hamilton is about **vertices** (every town once, like a delivery driver).

### Planar and isomorphic graphs

A graph is **planar** if it can be drawn with no edges crossing. For a connected planar graph, **Euler's formula** links vertices $v$, edges $e$ and faces $f$ (including the outside region):

$$v - e + f = 2$$

A cube's network has $v = 8$, $e = 12$ and $f = 6$: $8 - 12 + 6 = 2$.

Two graphs are **isomorphic** if they are the same network drawn differently: same number of vertices and edges, same degrees, and the same connections.

### Shortest paths

In a weighted network, the shortest path between two vertices has the smallest total weight.

*Diagram: Weighted network with vertices A to E. The shortest path from A to E is A, B, D, E with length 9*
*Shortest route from A to E: A, B, D, E with total 3 + 4 + 2 = 9.*

Other routes are longer: A, C, D, E is $2 + 8 + 2 = 12$ and A, B, E is $3 + 10 = 13$.

**Mind map**

```text
Networks
  Parts
    Vertices and edges
    Degree
    Sum of degrees = 2e
  Routes
    Walk, trail, path
    Circuit and cycle
  Euler
    Every edge once
    0 odd: circuit
    2 odd: trail
  Hamilton
    Every vertex once
  Planar
    No crossings
    v - e + f = 2
  Shortest path
    Smallest total weight
```

### Year 11: Counting edges in complete graphs
A **complete graph** $K_n$ joins every pair of its $n$ vertices. The number of edges is the number of ways to choose 2 vertices:

$$e = \binom{n}{2} = \frac{n(n - 1)}{2}$$

So $K_5$ has 10 edges. Each vertex has degree $n - 1$, and the sum of degrees, $n(n - 1)$, is twice the edge count, as it must be.

$K_5$ is not planar: no matter how you draw it, two edges cross. Euler's formula helps prove facts like this.

### Year 12: A shortest path method
For big networks, trying every route is too slow. **Dijkstra's method** finds shortest paths step by step:

1. Label the start 0 and every other vertex with "infinity".
2. From the current vertex, update each neighbour's label to the smallest of its old label and (current label + edge weight).
3. Mark the vertex with the smallest temporary label as final and make it current.
4. Repeat until the destination is final.

On the network above it labels B 3, C 2, D 7, then E 9. Map apps run methods like this many times a second.

## Quick summary

- A network has vertices and edges. Degree = number of edge ends at a vertex.
- Sum of degrees $= 2 \times$ edges, so odd vertices come in pairs.
- Euler circuit: 0 odd vertices. Euler trail: exactly 2 odd vertices, start and end at them.
- Hamiltonian paths visit every vertex once.
- Planar graphs: $v - e + f = 2$. Shortest path: the smallest total weight.

## Quiz

Try these questions from the chapter quiz.

1. The degree of a vertex is:
   - A. the number of vertices next to it
   - B. the number of edges meeting at it
   - C. its distance from the start
   - D. always even
   - Answer: B. the number of edges meeting at it. Count the edge ends at the vertex.

2. A network has 7 edges. The sum of its degrees is:
   - A. 7
   - B. 14
   - C. 3.5
   - D. 21
   - Answer: B. 14. $2 \times 7$.

3. A network has vertices of degree 2, 3, 3 and 4. How many edges does it have?
   - A. 12
   - B. 6
   - C. 4
   - D. 8
   - Answer: B. 6. Sum 12, so $12 \div 2$.

The whole chapter quiz is on the page, for signed-in students: https://whizznotes.com/mathematics-advanced/networks/#quiz