Introduction to Graph Theory

Graphs and their vocabulary (directed, undirected, weighted, simple), degrees and the handshaking lemma, walks, paths, cycles and connectivity, special graphs (complete, bipartite, trees and forests, DAGs), adjacency matrix and adjacency list representations with their costs, counting walks with matrix powers, Euler and Hamiltonian paths, planarity and Euler's formula, and colouring.

Graphs

A graph $G = (V, E)$ is a set of vertices (nodes) $V$ and edges $E$ connecting pairs of vertices. Graphs model networks of every kind: roads, social links, web pages, dependencies, state spaces in AI search.

Kind	Edges are
Undirected	unordered pairs $\{u, v\}$
Directed (digraph)	ordered pairs $(u, v)$ , "arcs"
Weighted	labelled with a cost/length $w(u, v)$
Simple	no self-loops, no parallel edges
Multigraph	parallel edges allowed

A simple undirected graph has at most $\binom n2 = \frac{n(n-1)}{2}$ edges; a simple digraph at most $n(n-1)$ . Dense graphs have $E = \Theta(V^2)$ ; sparse ones have $E = O(V)$ .

Degrees

Undirected: $\deg(v)$ = number of incident edges. Handshaking lemma: $\sum_v\deg(v) = 2\lvert E\rvert$ , so the number of odd-degree vertices is even.
Directed: in-degree and out-degree, with $\sum\deg^-(v) = \sum\deg^+(v) = \lvert E\rvert$ .
$k$ -regular: every vertex has degree $k$ (then $\lvert E\rvert = nk/2$ ).

Walks, paths, cycles, connectivity

Term	Definition
Walk	sequence of vertices joined by edges (repeats allowed)
Trail	walk with no repeated edge
Path	walk with no repeated vertex
Cycle	closed path (length ≥ 3 in simple graphs)
Connected	a path between every pair of vertices
Connected component	maximal connected subgraph
Strongly connected (digraph)	directed path both ways between every pair
Distance $d(u, v)$	length of a shortest path
Diameter	largest distance between two vertices

A graph with $n$ vertices and $c$ components has at least $n - c$ edges.

Special graphs

Complete, bipartite, tree and directed acyclic graphs.

Graph	Key facts
Complete $K_n$	$\binom n2$ edges, every vertex degree $n - 1$
Bipartite	vertices split into two sides, edges only across; ⇔ no odd cycle ⇔ 2-colourable; $K_{m,n}$ has $mn$ edges
Tree	connected, acyclic, $n - 1$ edges, a unique path between any two vertices; adding any edge creates exactly one cycle
Forest	acyclic; $n - c$ edges for $c$ trees
DAG	directed, no directed cycle; has a topological order
Cycle $C_n$ , path $P_n$	$n$ and $n - 1$ edges

A spanning tree of a connected graph is a subgraph that is a tree containing all vertices ( $n - 1$ edges). By Cayley's formula, $K_n$ has $n^{n-2}$ spanning trees.

Representations

Python

# vertices 0..3, undirected edges 0-1, 0-2, 1-2, 2-3
adj_list = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0],
]

Operation	Adjacency matrix	Adjacency list
Space	$\Theta(V^2)$	$\Theta(V + E)$
Is $(u, v)$ an edge?	$O(1)$	$O(\deg u)$
Iterate over neighbours of $u$	$\Theta(V)$	$\Theta(\deg u)$
Visit all edges	$\Theta(V^2)$	$\Theta(V + E)$
Best for	dense graphs, matrix algebra	sparse graphs, traversals

For undirected graphs the adjacency matrix is symmetric; for weighted graphs store $w(u, v)$ (∞ or None for no edge).

Counting walks: $(A^k)_{ij}$ is the number of walks of length exactly $k$ from $i$ to $j$ . $\operatorname{trace}(A^3)/6$ counts the triangles of an undirected graph.

Euler and Hamiltonian

	Euler (every edge once)	Hamiltonian (every vertex once)
Circuit/cycle exists	connected (ignoring isolated vertices) and all degrees even	no simple test — NP-complete
Path exists	exactly 0 or 2 vertices of odd degree	NP-complete
Algorithm	Hierholzer, $O(E)$	exhaustive search / DP $O(2^n n^2)$

Planarity and colouring

A graph is planar if it can be drawn without crossing edges. For connected planar graphs, Euler's formula $V - E + F = 2$ holds, and if $V \ge 3$ , $E \le 3V - 6$ ( $E \le 2V - 4$ if there are no triangles). Hence $K_5$ ( $E = 10 > 9$ ) and $K_{3,3}$ ( $E = 9 > 8$ ) are not planar.
A proper vertex colouring gives adjacent vertices different colours; the minimum number of colours is the chromatic number $\chi(G)$ . $\chi(K_n) = n$ ; $\chi = 2$ iff bipartite (with at least one edge); every planar graph is 4-colourable. Colouring models scheduling and register allocation.