Networks, Paths and Circuits

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.

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.

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.

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.

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

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