Graph Theory — Introduction

A vertex (plural: vertices) is a single point or node in a graph. A vertex set $V$ is the collection of all vertices. We write $|V|$ to mean the total number of vertices.

An edge connects two vertices. An edge set $E$ is the collection of all edges. Each edge is written as a pair $(u, v)$, meaning there is a connection between vertex $u$ and vertex $v$.

For example, in the graph $G = (V, E)$ where $V = \{1, 2, 3, 4\}$ and $E = \{(1,2), (1,3), (2,4), (3,4)\}$, there are 4 vertices and 4 edges.

In an undirected graph, edges have no direction. If there is an edge between $u$ and $v$, you can go from $u$ to $v$ AND from $v$ to $u$. The edge $(u, v)$ and $(v, u)$ are the same edge. Think of a two-way road between two cities, you can drive in either direction.

In a directed graph (also called a digraph), every edge has a direction, shown by an arrow. Edge $(u, v)$ means you can go from $u$ to $v$, but NOT necessarily from $v$ to $u$. Think of a one-way road: you can only drive in one direction.

In an unweighted graph, all edges are equal. We only care if an edge exists or not. In a weighted graph, each edge has a number called a weight (or cost). This weight can represent distance, time, cost, or capacity. For example, in a road map, the weight on each edge might be the distance in kilometres between two cities.

The degree of a vertex $v$ in an undirected graph is the number of edges connected to $v$. It is written as $\deg(v)$. A vertex with degree 0 is called an isolated vertex. A vertex with degree 1 is called a leaf or pendant vertex.

In a directed graph, each vertex $v$ has two degree values:

• In-degree $(\deg^-(v))$: number of edges coming into $v$ (arrows pointing to $v$).

• Out-degree $(\deg^+(v))$: number of edges going out of $v$ (arrows pointing away from $v$).

The Handshaking Lemma states that for any undirected graph $G = (V, E)$, \[ \sum_{v \in V} \deg(v) = 2|E| \] The sum of degrees of all vertices equals twice the number of edges. This is because every edge contributes exactly 2 to the total degree sum: one for each of its two endpoints. Counting degrees is like counting handshakes at a party: each handshake is counted once by each participant, so total counts = twice the handshakes.

Useful consequence: The number of vertices with odd degree is always even in any graph.

A complete graph $K_n$ is an undirected graph with $n$ vertices where every pair of distinct vertices is connected by exactly one edge. There is an edge between every possible pair.

The number of edges in $K_n$ is \[ |E| = \binom{n}{2} = \frac{n(n-1)}{2} \] because we choose 2 vertices from $n$ vertices for each edge. Also, every vertex in $K_n$ has degree $n-1$, since each vertex connects to all other $n-1$ vertices.

A DAG is a directed graph that has no directed cycles. That means, starting from any vertex, if you follow directed edges, you can never come back to the starting vertex. DAGs are used to represent dependencies, like course prerequisites, build systems, or scheduling tasks where some tasks must be done before others.

Key property: A DAG always has at least one vertex with in-degree 0 (no one points to it), called a source, and at least one vertex with out-degree 0 (it points to no one), called a sink.

A tree is a special graph that satisfies all three of these properties simultaneously:

• Undirected: edges have no direction.

• Connected: there is a path between every pair of vertices.

• Acyclic: there are no cycles.

From these three properties, a very important relationship follows automatically: \[ |E| = |V| - 1 \] A tree with $n$ vertices always has exactly $n-1$ edges. Remove any one edge and the tree becomes disconnected. Add any one edge and you create exactly one cycle.

An undirected graph is called connected if there is a path between every pair of vertices. That means you can reach any vertex from any other vertex by following edges.

A graph that is NOT connected is called disconnected. In a disconnected graph, there are groups of vertices that are isolated from each other. Each such group is called a connected component.

Formally, a connected component is a maximal set of vertices such that every pair of vertices in the set is connected by some path, and no vertex outside the set is connected to any vertex inside it.

A connected undirected graph with $n$ vertices needs at least $n - 1$ edges. This minimum is achieved exactly when the graph is a tree. \[ \text{connected graph:} \quad |E| \ge n - 1 \] Why: To connect $n$ vertices into a single group, we need enough edges to link every vertex, directly or indirectly, to every other. The most economical way (using the fewest edges) is a tree structure with exactly $n-1$ edges. Fewer than $n-1$ edges can never connect $n$ vertices, because each edge can merge at most 2 previously separate components into 1, so we need at least $n-1$ merging steps.

For an undirected graph with $n$ vertices, $m$ edges, and $c$ connected components, IF the graph is acyclic (a forest): \[ m = n - c \] This generalizes the tree formula ($|E| = |V| - 1$, i.e., $c=1$) to the case of multiple components. Each component, being a tree, contributes (its own vertices $-1$) edges, and summing over all components gives $n - c$ total edges.

If the graph is not necessarily acyclic, then instead we only know: \[ m \ge n - c \] with equality holding if and only if every component is a tree (no cycles anywhere).

A directed graph is called strongly connected if for every pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$. In simple words, you can reach every vertex from every other vertex by following the directed edges.

A Strongly Connected Component (SCC) is a maximal subset of vertices that are all mutually reachable from each other.

A directed graph is called weakly connected if the underlying undirected graph (obtained by ignoring all arrow directions) is connected. So weakly connected means connected if we pretend all edges are two-way. Weakly connected does NOT require paths in both directions.

For any directed graph: \[ \text{Strongly Connected} \implies \text{Weakly Connected} \] But the reverse is NOT true, weakly connected does not imply strongly connected (as shown in the example above).

Special case: If a directed graph has no edges at all between any pair of vertices (i.e., it's just isolated vertices), it is neither strongly nor weakly connected (unless it has just 1 vertex, in which case it is trivially both).

A walk is a finite alternating sequence of vertices and edges, where consecutive vertices are joined by the edge between them. Both vertices and edges are allowed to repeat freely in a walk. The length of a walk is the number of edges covered in it.

A walk is called open if its length is greater than 0 and the starting and ending vertices are different. A walk is called closed if its length is greater than 0 and the starting and ending vertices are the same. A walk of length 0 (a single vertex, no edges) is called a trivial walk.

A trail is an open walk in which vertices may repeat, but edges are not allowed to repeat. Think of a trail as a walk with one extra restriction: once you have used a particular road, you cannot use that exact road again, but you are still allowed to revisit the same junction.

A circuit is a closed walk in which vertices may repeat, but edges are not allowed to repeat. In other words, a circuit is simply a trail that returns to its starting vertex. A closed trail is called a circuit.

A path is an open walk in which neither vertices (except possibly the starting and ending vertex) nor edges are allowed to repeat. This is the strictest form of an open walk: every vertex is visited at most once, so naturally every edge is also used at most once (since repeating an edge would force repeating a vertex).

A cycle is a closed walk in which neither vertices nor edges are allowed to repeat, except that the starting and ending vertex is the same. In other words, a cycle is a closed path. A closed path is called a cycle.

Given a list of numbers, a natural question is: can we build a simple undirected graph where these numbers are exactly the degrees of the vertices? Such a sequence is called a graphical sequence (or graphic sequence). Not every sequence of numbers is graphical; some sequences simply cannot correspond to any real graph, however hard we try to draw edges. The Havel–Hakimi algorithm gives us a step-by-step method to test this, without needing to try every possible graph.

A degree sequence $d_1 \ge d_2 \ge \cdots \ge d_n \ge 0$ (sorted in non-increasing order) is graphical if and only if the sequence \[ (d_2 - 1, d_3 - 1, \ldots, d_{d_1+1} - 1, d_{d_1+2}, \ldots, d_n) \] obtained by removing the largest value $d_1$ and subtracting 1 from the next $d_1$ largest entries, is also graphical.

In plain words: take the vertex with the highest degree, say $d_1$. Connect it to the $d_1$ next-highest-degree vertices (this is always possible, and always the safest choice). Once that vertex is fully connected, remove it from the list, and reduce the degree of each vertex it was connected to by 1 (since each of those vertices has now used up one of its edges). Repeat this process on the smaller sequence.

At each step of the algorithm, sort the sequence in non-increasing order first. Then check:

• If all remaining values are 0, the sequence is graphical. Stop.

• If the largest value $d_1$ is greater than the number of remaining entries (excluding itself), the sequence is NOT graphical. Stop (there simply aren't enough other vertices to connect to).

• If subtracting 1 produces any negative value, the sequence is NOT graphical. Stop.

• Otherwise, repeat the reduction step on the new sequence.

An adjacency matrix is a 2D array (matrix) of size $|V| \times |V|$. For a graph with $|V| = n$ vertices numbered $1$ to $n$: \[ A[i][j] = \begin{cases} 1 & \text{if there is an edge from vertex } i \text{ to vertex } j \\ 0 & \text{otherwise} \end{cases} \] For a weighted graph, we store the weight instead of 1. For an undirected graph, the matrix is always symmetric, meaning $A[i][j] = A[j][i]$.

Space: $O(V^2)$, regardless of the number of edges.

Edge check: $O(1)$, since $A[u][v]$ gives the answer directly.

Finding all neighbours of $v$: $O(V)$, since we must scan the entire row $v$.

An adjacency list stores, for each vertex $v$, a list of all vertices adjacent to $v$ (its neighbours). We can implement this as an array of linked lists, or as an array of Python lists.

Space: $O(V + E)$, since we store $|V|$ list headers and $2|E|$ total entries (each edge appears in two lists for undirected graph, or $|E|$ entries total for directed).

Edge check: $O(\deg(v))$, we must scan the list of $v$ to see if $u$ is in it.

Finding all neighbours of $v$: $O(\deg(v))$, simply iterate the list.

Total traversal: $O(V + E)$, visiting all vertices and all their edges.

A dense graph has many edges, close to the maximum possible. A complete graph $K_n$ is the densest possible, with $n(n-1)/2$ edges. For dense graphs, $|E| \approx |V|^2$, so adjacency matrix wastes little space and makes edge checks very fast.

A sparse graph has few edges, much less than the maximum. For sparse graphs, $|E| \ll |V|^2$, often $|E| \approx |V|$ or $|E| \approx |V| \log |V|$. Adjacency list is much better here because the matrix would be mostly empty zeros, wasting memory.

When we run graph traversal algorithms like BFS or DFS:

• Using adjacency matrix: For each vertex $v$, we scan its entire row to find neighbours. This takes $O(V)$ per vertex, and with $V$ vertices total, the whole traversal takes $O(V^2)$.

• Using adjacency list: For each vertex $v$, we only look at the neighbours in its list. The total work across all vertices is proportional to the total number of entries in all lists, which equals $2|E|$ (each edge appears twice for undirected). So total traversal takes $O(V + E)$.

For sparse graphs where $|E| \ll |V|^2$, the adjacency list traversal $O(V+E)$ is much faster than matrix traversal $O(V^2)$.