Graph Terminology

Vertices and Edges

A graph $G = (V, E)$ consists of a set of vertices (nodes) $V$ and a set of edges (arcs) $E \subseteq V \times V$. We only consider finite graphs where $|V|$ and $|E|$ are finite.

Directed graphs have ordered pairs $(u, v) \in E$, drawn with an arrow from $u$ (tail) to $v$ (head). $u$ is the source and $v$ the destination of the edge. Undirected graphs have unordered pairs (or the edge relation is symmetric); an undirected edge $\{u, v\}$ is conceptually equivalent to having both directed edges $(u, v)$ and $(v, u)$.

A simple graph has no self-loops (edges from a vertex to itself: $(v, v)$) and no parallel edges (multiple edges between the same ordered pair of vertices). Unless stated otherwise, the syllabus deals with simple graphs. A multigraph allows parallel edges; a pseudograph also allows self-loops.

A weighted graph associates a real number with each edge via a function $w: E \to \mathbb{R}$. Weights represent cost, distance, time, capacity, or any additive metric. Unweighted graphs can be considered as having unit weight on every edge.

Degree

The degree $\deg(v)$ of a vertex in an undirected graph is the number of edges incident at that vertex. In directed graphs:

• In-degree $\deg^{-}(v)$: number of edges entering $v$.
• Out-degree $\deg^{+}(v)$: number of edges leaving $v$.

Handshaking lemma: For an undirected graph, $\sum_{v \in V} \deg(v) = 2|E|$. For directed graphs, $\sum \deg^{-}(v) = \sum \deg^{+}(v) = |E|$. A corollary: the number of odd-degree vertices in any undirected graph is always even.

Paths, Walks, and Cycles

A walk is any sequence of vertices where consecutive pairs are edges. A trail is a walk with no repeated edges. A path is a walk with no repeated vertices (except possibly the first/last). A simple path has no repeated vertices at all. The length of an unweighted path is the number of edges traversed ($k-1$ for $k$ vertices). For weighted graphs, the path length is the sum of edge weights along the path.

A cycle (or circuit) is a path of length at least 1 that starts and ends at the same vertex with no other vertex repeated. A graph with no cycles is acyclic.

Connectivity

An undirected graph is connected if there exists a path between every pair of vertices. A connected component is a maximal connected subgraph. The components partition the vertex set.

For directed graphs, we distinguish:

• Weak connectivity: the underlying undirected graph (ignoring edge directions) is connected.
• Strong connectivity: for every ordered pair $(u, v)$, there is a directed path from $u$ to $v$.

Subgraphs

• Subgraph: $G' = (V', E')$ with $V' \subseteq V$ and $E' \subseteq E$.
• Induced subgraph: select $V' \subseteq V$ and include all edges from $E$ whose both endpoints are in $V'$.
• Spanning subgraph: $V' = V$ (contains all vertices, subset of edges).

Trees and Forests

A free tree (or simply tree) is a connected, acyclic undirected graph. Equivalent characterisations for a graph with $n$ vertices:

1. Connected and has exactly $n-1$ edges.
2. Acyclic and has exactly $n-1$ edges.
3. Any two vertices are connected by exactly one simple path.
4. Connected, and removing any edge disconnects the graph (minimally connected).
5. Acyclic, and adding any edge creates exactly one cycle (maximally acyclic).

A forest is an acyclic undirected graph (a collection of disjoint trees). A forest with $c$ components has $n-c$ edges.

Density

Classification	Edge count	Example
Sparse	$\lvert E \rvert = O(\lvert V \rvert)$	Road network, planar graph
Dense	$\lvert E \rvert = \Theta(\lvert V \rvert^2)$	Complete graph $K_n$

A complete graph has $|E| = \binom{n}{2} = \frac{n(n-1)}{2}$. Most real-world graphs are sparse.

Example

Consider a road network: Cambridge (C), Oxford (O), London (L), York (Y). Roads: C—O (80), C—L (55), L—Y (210).

• $V = \{C, O, L, Y\}$, $|V|=4$. $E = \{(C,O), (C,L), (L,Y)\}$, $|E|=3$.
• $\deg(C)=2$, $\deg(O)=1$, $\deg(L)=2$, $\deg(Y)=1$.
• The graph is connected but not complete (missing 3 possible edges).
• $|E| = 3 = O(4)$, so it is sparse.

Summary

Term	Definition
Graph	$G = (V, E)$
Directed	Ordered pairs $(u, v)$
Undirected	Unordered pairs $\{u, v\}$
Simple graph	No self-loops, no parallel edges
Weighted graph	$w: E \to \mathbb{R}$
Degree	Incident edges per vertex
Path	Sequence of distinct vertices connected by edges
Cycle	Closed path, no vertex repeated except start=end
Connected	Path exists between every pair
Tree	Connected and acyclic; $\lvert E \rvert = \lvert V \rvert - 1$
Sparse	$\lvert E \rvert = O(\lvert V \rvert)$
Dense	$\lvert E \rvert = \Theta(\lvert V \rvert^2)$

Past paper questions: y2025p1q9 (connected components, BFS on adjacency matrix).