Graph Theory Textbook
From the definition of a graph to planarity, coloring, and matroids. A textbook series building definitions, theorems, and proofs in a systematic progression.
Graph Theory: A Complete Summary of Definitions, Theorems, and Proofs
A single-article overview of graph theory, from basic definitions through planarity, coloring, and matroids. Covers all the key definitions, theorems, and algorithms needed for discrete mathematics and competitive programming, organized with a topic dependency diagram.
Fundamental Definitions and Basic Properties of Graphs
Starting from the formal definitions of undirected and directed graphs, we develop the notions of degree, the handshaking lemma, complete graphs $K_n$, complete bipartite graphs $K_{m,n}$, and graph isomorphism, with full proofs throughout.
Paths and Connectivity
We formalize the notions of walks, paths, and cycles, then develop the theory of connected components, vertex and edge connectivity, cut vertices and bridges, the characterization of bipartite graphs, and Menger's theorem.
Trees and Forests: The Minimal Connected Structures
We prove the equivalent characterizations of trees, establish the formula $|E|=|V|-1$, introduce rooted trees and Cayley's formula, and develop the theory of spanning trees and minimum spanning trees via Kruskal's and Prim's algorithms.
Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems
From the Bridges of Königsberg to Euler's theorem on Eulerian circuits, directed Eulerian graphs, Hamiltonian cycles, the theorems of Ore and Dirac, and the NP-completeness of the Hamiltonian cycle problem.
Shortest Path Problems in Weighted Graphs
A systematic treatment of shortest path algorithms: BFS for unweighted graphs, Dijkstra's algorithm with a correctness proof, the Bellman--Ford algorithm with negative-cycle detection, the Floyd--Warshall algorithm, and shortest paths in DAGs.
Directed Graphs and Topological Sorting
Strongly connected components (SCCs), Tarjan's and Kosaraju's algorithms, DAGs and topological sorting, the correspondence with partial orders, and dynamic programming on DAGs.
Matchings and Coverings
Augmenting paths, Berge's theorem, Hall's marriage theorem, König's theorem, stable matchings via the Gale--Shapley algorithm, and weighted matchings --- all with complete proofs.
Network Flows
Flow networks, the max-flow min-cut theorem, the Ford--Fulkerson method, the Edmonds--Karp algorithm, Dinic's algorithm, and the reduction of bipartite matching to maximum flow.
Planar Graphs
Euler's polyhedral formula $V - E + F = 2$, the bound $E \leq 3V - 6$, non-planarity of $K_5$ and $K_{3,3}$, Kuratowski's theorem, and dual graphs.
Graph Coloring
The chromatic number $\chi(G)$, greedy coloring, Brooks' theorem, the chromatic polynomial, edge coloring and Vizing's theorem, and an overview of the four color theorem.
Introduction to Algebraic Graph Theory
The adjacency matrix, the Laplacian $L = D - A$, the matrix tree theorem, eigenvalues and connectivity, and a proof that the $(i,j)$-entry of $A^k$ counts the number of walks of length $k$.
Matroids and the Greedy Algorithm
The axioms of a matroid, the graphic matroid, the optimality theorem for the greedy algorithm, a reinterpretation of MST algorithms, and matroid intersection.