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.

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.

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