Introduction to Graph Theory Concepts

Graph theory provides the mathematical framework for solving real-world routing and optimisation problems. Before diving into the algorithms themselves, we need a precise vocabulary for describing how we move through a graph.

Undirected Graph: A set of vertices (nodes) connected by edges, where the edges have no direction , you can traverse them in either direction.

The key distinctions between types of traversals are:

Walk: A sequence of vertices and edges where both vertices and edges may be repeated.
Trail: A walk in which no edge is repeated (vertices may still repeat).
Path: A walk in which no vertex is repeated (and therefore no edge is repeated either).
Circuit: A trail that starts and ends at the same vertex.
Cycle: A path that starts and ends at the same vertex (so no repeated vertices except the start/end).

Analogy

Think of a city street map. A walk is any journey through streets , you can use the same road twice. A trail means you never drive the same road twice, but you might pass through the same intersection. A path means you never even revisit the same intersection. A circuit or cycle is any of these that brings you back home.

Example

Consider a graph with vertices ${A, B, C, D, E}$ and edges: $A$ – $B$ , $B$ – $C$ , $C$ – $D$ , $D$ – $E$ , $A$ – $D$ , $B$ – $D$ .

Walk: $A \to B \to C \to B \to D \to E$ (vertex $B$ and edge $B$ – $C$ then $B$ revisited)
Trail: $A \to B \to C \to D \to A$ (no edge repeated, but note $A$ appears as start)
Path: $A \to B \to C \to D \to E$ (no vertex repeated)
Circuit: $A \to B \to D \to A$ (trail returning to start , no repeated edges, vertices may repeat only at start/end)
Cycle: $A \to B \to D \to A$ (path returning to start , no repeated vertices except start/end)

Note: Every cycle is a circuit, but not every circuit is a cycle. A circuit only forbids repeated edges; a cycle also forbids repeated vertices (other than the start/end).

Eulerian Trails and Circuits

Eulerian Trail: A trail that uses every edge in a graph exactly once.

Eulerian Circuit: An Eulerian trail that starts and ends at the same vertex , every edge is used exactly once and the route forms a closed loop.

The existence of Eulerian trails and circuits depends entirely on the degrees of the vertices.

Degree of a Vertex: The number of edges connected to that vertex.

The conditions are clean and testable:

Eulerian circuit exists $\Leftrightarrow$ the graph is connected and every vertex has even degree.
Eulerian trail exists (but not a circuit) $\Leftrightarrow$ the graph is connected and exactly two vertices have odd degree (these are forced to be the start and end vertices).

Note

If a graph has 0 odd-degree vertices, an Eulerian circuit exists. If it has exactly 2 odd-degree vertices, an Eulerian trail (but not a circuit) exists. If it has 4 or more odd-degree vertices, neither exists without modification.

Example

A graph has edges: $A$ – $B$ , $A$ – $C$ , $B$ – $C$ , $B$ – $D$ , $C$ – $D$ .

Calculate each degree:

$de g (A) = 2$ (even)
$de g (B) = 3$ (odd)
$de g (C) = 3$ (odd)
$de g (D) = 2$ (even)

There are exactly 2 odd-degree vertices ( $B$ and $D$ ), so an Eulerian trail exists starting at $B$ and ending at $D$ (or vice versa), but no Eulerian circuit.

Exam Tip

To quickly check for Eulerian properties: count the odd-degree vertices. Zero → circuit. Two → trail. Four or more → need the Chinese Postman approach.

Free preview

11 more sections in this topic

Introduction to Graph Theory Concepts

Undirected Graph: A set of vertices (nodes) connected by edges, where the edges have no direction , you can traverse them in either direction.

The key distinctions between types of traversals are:

Walk: A sequence of vertices and edges where both vertices and edges may be repeated.
Trail: A walk in which no edge is repeated (vertices may still repeat).
Path: A walk in which no vertex is repeated (and therefore no edge is repeated either).
Circuit: A trail that starts and ends at the same vertex.
Cycle: A path that starts and ends at the same vertex (so no repeated vertices except the start/end).

Analogy

Example

Consider a graph with vertices ${A, B, C, D, E}$ and edges: $A$ – $B$ , $B$ – $C$ , $C$ – $D$ , $D$ – $E$ , $A$ – $D$ , $B$ – $D$ .

Walk: $A \to B \to C \to B \to D \to E$ (vertex $B$ and edge $B$ – $C$ then $B$ revisited)
Trail: $A \to B \to C \to D \to A$ (no edge repeated, but note $A$ appears as start)
Path: $A \to B \to C \to D \to E$ (no vertex repeated)
Circuit: $A \to B \to D \to A$ (trail returning to start , no repeated edges, vertices may repeat only at start/end)
Cycle: $A \to B \to D \to A$ (path returning to start , no repeated vertices except start/end)

Note: Every cycle is a circuit, but not every circuit is a cycle. A circuit only forbids repeated edges; a cycle also forbids repeated vertices (other than the start/end).

Eulerian Trails and Circuits

Eulerian Trail: A trail that uses every edge in a graph exactly once.

Eulerian Circuit: An Eulerian trail that starts and ends at the same vertex , every edge is used exactly once and the route forms a closed loop.

The existence of Eulerian trails and circuits depends entirely on the degrees of the vertices.

Degree of a Vertex: The number of edges connected to that vertex.

The conditions are clean and testable:

Eulerian circuit exists $\Leftrightarrow$ the graph is connected and every vertex has even degree.
Eulerian trail exists (but not a circuit) $\Leftrightarrow$ the graph is connected and exactly two vertices have odd degree (these are forced to be the start and end vertices).

Note

Example

A graph has edges: $A$ – $B$ , $A$ – $C$ , $B$ – $C$ , $B$ – $D$ , $C$ – $D$ .

Calculate each degree:

$de g (A) = 2$ (even)
$de g (B) = 3$ (odd)
$de g (C) = 3$ (odd)
$de g (D) = 2$ (even)

There are exactly 2 odd-degree vertices ( $B$ and $D$ ), so an Eulerian trail exists starting at $B$ and ending at $D$ (or vice versa), but no Eulerian circuit.

Exam Tip

To quickly check for Eulerian properties: count the odd-degree vertices. Zero → circuit. Two → trail. Four or more → need the Chinese Postman approach.

Free preview

AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman

Introduction to Graph Theory Concepts

Eulerian Trails and Circuits

11 more sections in this topic

AHL 3.16—Tree and cycle algorithms, Chinese postman, travelling salesman

Introduction to Graph Theory Concepts

Eulerian Trails and Circuits

11 more sections in this topic