Finite graphs: vertices, edges, paths, cycles, trees, planarity, colouring, matching, flows. Discrete-math foundation for network science, algorithms, and combinatorial optimisation.
graph-theory
Graph G = (V, E)
A finite set of vertices V and edges E ⊆ V × V. Simple, undirected unless stated otherwise. Directed graphs and multigraphs are variants.
Path
A sequence v₀, v₁, …, v_k of vertices with each consecutive pair an edge and no vertex repeated.
Cycle
A closed path: v₀ = v_k with v₁, …, v_{k-1} distinct. A graph without cycles is a forest.
Tree (graph-theoretic)
A connected graph with no cycles. Equivalently, n vertices and n−1 edges. Spanning trees underlie MST algorithms (Prim, Kruskal).
Planar graph
A graph that can be drawn in the plane without edge crossings. Kuratowski: a graph is planar ⇔ it contains no subdivision of K₅ or K₃,₃.
Four-colour theorem
Every planar graph can be properly vertex-coloured with ≤ 4 colours. First major theorem proved by computer (Appel-Haken, 1976;…
Euler circuit
A closed walk traversing every edge exactly once. Exists iff the graph is connected and every vertex has even degree (Euler, 1736,…
Hamilton cycle
A cycle visiting every vertex exactly once. Deciding existence is NP-complete in general; many sufficient conditions (Dirac, Ore).
Max-flow min-cut theorem
In a flow network, the maximum value of an s-t flow equals the minimum capacity of an s-t cut. Ford-Fulkerson (1956). Dualises to bipartite…
Graph colouring
An assignment of colours to vertices so that adjacent vertices differ. Chromatic number χ(G) is NP-hard to compute. Related to scheduling,…
Bipartite graph
A graph whose vertex set partitions as V = A ⊔ B with every edge between A and B. Characterisation: no odd cycles (König). Models…
Matching
A set of edges no two sharing a vertex. König's theorem: in bipartite graphs, max matching = min vertex cover. Hall's marriage theorem:…
Shortest path
A path P from s to t minimising Σ w(e) over edges. Dijkstra (non-neg weights, O((V+E)log V)), Bellman–Ford (general weights, O(VE)),…
Spanning tree
A subgraph of G that is a tree and contains every vertex. Minimum spanning tree: weights sum minimised — Kruskal/Prim. Counted by…
Euler's polyhedral formula
For a connected planar graph V − E + F = 2, where F counts faces (including the outer). Generalises to χ = V − E + F for any 2-manifold.
Chromatic polynomial
P(G, k) counts proper k-colourings of G; a polynomial of degree |V| with integer coefficients. Recurrence P(G,k) = P(G−e, k) − P(G/e, k)…
Random graph (Erdős–Rényi)
Probability model G(n, p): n vertices, each edge included independently with probability p. Sharp threshold phenomena (connectivity at…
Spectral graph theory
Study of graphs via the spectra of their adjacency matrix A and Laplacian L = D − A. λ_2(L) (algebraic connectivity) controls expansion;…
Eulerian trail/circuit
Connected graph has Eulerian circuit iff every vertex has even degree; Eulerian trail iff exactly 0 or 2 odd-degree vertices. Königsberg…
Hamiltonian cycle / Dirac theorem
Dirac 1952: n ≥ 3, min degree ≥ n/2 ⟹ Hamiltonian. Ore generalization min deg sum ≥ n. Hamiltonicity NP-complete (Karp).
Menger's theorem
Min cut between s,t = max flow from s to t (vertex or edge version). Max-flow min-cut as generalization. Basic connectivity result.
Ramsey numbers R(m,n)
Smallest N such that any 2-coloring of K_N contains red K_m or blue K_n. R(3,3)=6, R(4,4)=18, R(5,5) ∈ [43,48]. Probabilistic bounds…
Turán's theorem
Max edges in K_{r+1}-free graph on n vertices is T(n,r) = (1 − 1/r) n²/2, achieved by Turán graph. Extremal graph theory pillar.
Kuratowski theorem
G planar iff contains no subdivision of K_5 or K_{3,3}. Wagner version: no K_5 or K_{3,3} as minor. Euler formula V − E + F = 2.
Robertson-Seymour minor theorem
Graph minors form well-quasi-order: any infinite family contains H ≤ G. Polynomial recognition for every minor-closed class.
Chromatic number & Brooks' theorem
χ(G) ≤ Δ(G) for connected graph except K_n and odd cycle (Brooks 1941). Mycielski: triangle-free graphs of arbitrarily high χ.
Perfect graph theorem
G perfect (χ = ω on every induced subgraph) iff G has no odd hole / antihole (Chudnovsky et al 2006). Lovász 1972 (weak PGT).
Expander graph
Sparse highly-connected graph: h(G) ≥ c. Explicit: Lubotzky-Phillips-Sarnak Ramanujan graphs. Derandomization, extractors, error-correcting…
Dijkstra / Bellman-Ford / Floyd-Warshall
Shortest-path algorithms: Dijkstra O(E log V) non-neg weights; Bellman-Ford O(VE) negative allowed; Floyd-Warshall O(V³) all-pairs.
Minimum spanning tree (Kruskal/Prim)
Kruskal O(E log V) sorted edges + union-find; Prim O(E log V) with binary heap. Matroid-greedy; Borůvka's parallel algorithm.
Hall's marriage theorem
In a bipartite graph G = (X ⊔ Y, E), a matching saturating X exists iff for every subset S ⊆ X, |N(S)| ≥ |S|. The 'Hall condition' is both…
König's theorem (bipartite)
In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. LP-duality statement for bipartite…
Brooks' theorem
For a connected graph G, the chromatic number χ(G) ≤ Δ(G) (the maximum degree) unless G is a complete graph or an odd cycle. Tightens the…
Vizing's theorem
Every simple graph has edge chromatic number χ'(G) ∈ {Δ, Δ+1} where Δ is the maximum degree. Class-1 graphs attain Δ (e.g. K_n for n…
Kuratowski's theorem
A finite graph is planar iff it does not contain a subdivision of K_5 or K_{3,3} as a subgraph. Wagner's theorem is the minor-closed…
Dirac's theorem (Hamiltonicity)
Dirac 1952: a simple graph on n ≥ 3 vertices with minimum degree at least n/2 contains a Hamilton cycle. Sharp at C_n for n = 4. Ore's…
Tutte's perfect-matching theorem
Tutte 1947: G has a perfect matching iff for every vertex subset S, the number of odd components of G − S is at most |S|. Generalises Hall…
Friendship theorem
Erdős-Rényi-Sós 1966: a finite graph in which every two distinct vertices have exactly one common neighbour is a windmill graph F_n (one…