Graph Theory

Graph theory is the mathematical study of pairwise relationships between objects. Networks, dependency trees, social graphs, routing tables, and state machines are all graphs. The formal definitions give you precise tools for reasoning about them.

Formal Definition

A graph G = (V, E) consists of:

• V: a set of vertices (nodes)
• E: a set of edges, where each edge connects two vertices

V = {A, B, C, D}
E = {(A,B), (B,C), (C,D), (A,D)}

Directed graph (digraph): edges are ordered pairs (A → B ≠ B → A).

Undirected graph: edges are unordered pairs ({A,B} = {B,A}).

Weighted graph: each edge has a numerical weight (cost, distance, capacity).

Basic Definitions

Degree of a vertex: number of edges incident to it.

• In a directed graph: in-degree (edges coming in) and out-degree (edges going out).

Handshaking lemma: the sum of all degrees in an undirected graph = 2|E|. Every edge contributes to exactly two vertices' degrees.

Path: a sequence of vertices where each consecutive pair is connected by an edge.

Simple path: a path with no repeated vertices.

Cycle: a path that starts and ends at the same vertex.

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

Complete graph Kₙ: every pair of vertices is connected. Has n(n-1)/2 edges.

Trees

A tree is a connected undirected graph with no cycles. Key property: a tree with n vertices has exactly n-1 edges.

Equivalent definitions of a tree (any one implies the others):

1. Connected and acyclic
2. Connected with n-1 edges
3. Acyclic with n-1 edges
4. Any two vertices are connected by exactly one simple path

Spanning tree of a graph: a subgraph that includes all vertices and is a tree. Used in network design to connect all nodes with minimum edges.

Minimum spanning tree (MST): a spanning tree with minimum total edge weight. Algorithms:

• Kruskal's: sort edges by weight; greedily add edges that don't create cycles. O(E log E).
• Prim's: start from any vertex; greedily add the cheapest edge connecting the tree to a new vertex. O(E log V) with a priority queue.

Euler and Hamiltonian Paths

Euler Path and Circuit

An Euler path visits every edge exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex.

Königsberg Bridge Problem (1736): Euler proved that a path crossing all seven bridges of Königsberg exactly once was impossible — founding graph theory.

Existence conditions:

• Euler circuit exists ↔ every vertex has even degree
• Euler path exists ↔ exactly 0 or 2 vertices have odd degree

Application: route optimisation (garbage collection trucks, mail delivery) — visit every street exactly once.

Hamiltonian Path and Circuit

A Hamiltonian path visits every vertex exactly once. A Hamiltonian circuit returns to the start.

No simple characterisation exists (unlike Euler). Finding one is NP-complete — no polynomial algorithm is known. The Travelling Salesman Problem (TSP) is finding the shortest Hamiltonian circuit in a weighted graph.

Connectivity

Cut vertex (articulation point): a vertex whose removal disconnects the graph. Identifying these is critical in network reliability analysis.

Bridge: an edge whose removal disconnects the graph.

k-connected: a graph where at least k vertices must be removed to disconnect it. The internet is designed to be highly connected for resilience.

Strongly connected component (SCC): in a directed graph, a maximal set of vertices where every vertex is reachable from every other. SCCs can be found in O(V + E) with Tarjan's or Kosaraju's algorithm.

# Simple connectivity check with DFS
def is_connected(graph, start, n):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])
    return len(visited) == n

Bipartite Graphs

A graph is bipartite if its vertices can be split into two sets U and V such that every edge connects a vertex in U to a vertex in V (no edges within the same set).

Test for bipartiteness: a graph is bipartite if and only if it contains no odd-length cycles. BFS/DFS with 2-colouring detects this in O(V + E).

from collections import deque

def is_bipartite(graph, n):
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbour in graph[node]:
                if color[neighbour] == -1:
                    color[neighbour] = 1 - color[node]
                    queue.append(neighbour)
                elif color[neighbour] == color[node]:
                    return False
    return True

Applications: matching problems (job assignments, marriage matching), scheduling (conflict-free colouring), and recommendation systems.

Planar Graphs

A graph is planar if it can be drawn in a plane without edges crossing. Circuit boards are planar when routes don't cross layers.

Euler's formula for planar graphs: V − E + F = 2, where F is the number of faces (including the outer infinite face).

For a connected planar graph with V ≥ 3: E ≤ 3V − 6. This means dense graphs (many edges) cannot be planar.

K₅ (5 vertices, all connected) and K₃,₃ (bipartite with 3+3 vertices, all connected) are the two minimal non-planar graphs — Kuratowski's theorem states every non-planar graph contains one of these as a subgraph.

Graph Colouring

A proper colouring assigns a colour to each vertex so no two adjacent vertices share a colour. The minimum number of colours needed is the chromatic number χ(G).

Four Colour Theorem: every planar graph can be coloured with at most 4 colours (proved 1976, first major computer-assisted proof).

Applications:

• Register allocation in compilers: variables are vertices, edges represent simultaneous usage, colours are registers.
• Scheduling: tasks are vertices, conflicts are edges, colours are time slots.
• Map colouring: countries are vertices, shared borders are edges.

Key Takeaways

• A graph G = (V, E) formalises pairwise relationships. Trees are connected acyclic graphs with n-1 edges.
• Euler circuits require all vertices to have even degree. Hamiltonian circuits are NP-complete to find.
• Minimum spanning trees (Kruskal's, Prim's) connect all vertices with minimum total weight.
• Bipartite graphs have no odd cycles and model assignment/matching problems.
• Graph colouring (chromatic number) models register allocation, scheduling, and conflict resolution.