Features of Graphs: Paths, Weighted Path Lengths, Cycles, and Subgraphs

Paths

A path in a graph is a sequence of vertices $v_0, v_1, v_2, \ldots, v_k$ such that there is an edge between each consecutive pair $(v_{i-1}, v_i)$.

Simple Path

A simple path visits each vertex at most once. Most algorithms (e.g. shortest path) search for simple paths.

Path in Directed Graphs

In a directed graph, the path must follow edge directions: each edge $(v_{i-1}, v_i)$ must point from $v_{i-1}$ to $v_i$.

Example:

A → B → D → E

This is a path of length 3 from A to E (passing through B and D).

KEY TAKEAWAY: A path defines a route through the graph. The length of a path depends on whether the graph is weighted or unweighted.

Path Length

Unweighted Path Length

In an unweighted graph, the length of a path is the number of edges it contains.

$$\text{length}(v_0, v_1, \ldots, v_k) = k$$

Weighted Path Length

In a weighted graph, the weighted path length (also called the cost or weight of the path) is the sum of the edge weights along the path.

$$\text{weighted_length}(v_0, v_1, \ldots, v_k) = \sum_{i=1}^{k} w(v_{i-1}, v_i)$$

Example:

A --3--> B --7--> D
A --3--> B → weighted path length = 3
A --3--> B --7--> D → weighted path length = 10

EXAM TIP: Shortest path algorithms like Dijkstra’s minimise the weighted path length, not the number of edges.

Cycles

A cycle is a path that starts and ends at the same vertex, with no repeated edges.

• In an undirected graph: a cycle is a closed path of length $\geq 3$.
• In a directed graph: a cycle follows edge directions and returns to the start.

Example of a cycle:

A → B → C → A

This is a directed cycle of length 3.

Why Cycles Matter

• Directed Acyclic Graphs (DAGs) have no cycles — important for topological ordering.
• Negative-weight cycles in Dijkstra’s make shortest paths undefined (Bellman-Ford detects these).
• Trees are acyclic connected graphs.

Subgraphs

A subgraph $G’ = (V’, E’)$ of a graph $G = (V, E)$ is a graph where:
- $V’ \subseteq V$ (a subset of vertices)
- $E’ \subseteq E$ (a subset of edges, but only between vertices in $V’$)

Spanning Subgraph

A spanning subgraph includes all vertices of $G$ but only some edges.

Spanning Tree

A spanning tree of a connected graph $G$ is a spanning subgraph that is also a tree (connected and acyclic). Prim’s algorithm finds a minimum spanning tree — the spanning tree with minimum total edge weight.

VCAA FOCUS: Be able to identify paths, weighted path lengths, and cycles in a given graph diagram. Know why subgraphs (especially spanning trees) are useful in network optimisation problems.

Summary