Graph Theory¶
Job: Formalize graphs and their invariants; state connectivity, matching, and minor-closed structure theorems at research-usable precision.
Core¶
Graph \(G=(V,E)\) (simple undirected unless stated). Order \(n=|V|\), size \(m=|E|\). Degree sum \(2m\). Isomorphism: bijection preserving adjacency.
Paths / cycles / connectivity: \(G\) connected iff \(u\)–\(v\) path for all pairs. Cutvertex / bridge. Menger: local connectivity \(\kappa(u,v)=\) max number of internally vertex-disjoint \(u\)–\(v\) paths.
Trees: connected acyclic \(\Leftrightarrow\) unique paths \(\Leftrightarrow\) \(m=n-1\) and connected. Cayley: \(n^{n-2}\) labeled trees on \(n\) vertices.
Euler / Hamilton: Eulerian circuit iff connected (ignore isolates) and all degrees even. Hamiltonicity NP-complete; Dirac \(n\ge3\), \(\delta\ge n/2\Rightarrow\) Hamiltonian; Ore refinement.
Matchings: Hall's marriage theorem for bipartite \(G\): system of distinct reps iff \(|N(S)|\ge|S|\) all \(S\subseteq A\). König: bipartite matching number \(=\) vertex cover number. Tutte's \(f\)-factor criterion in general graphs.
Coloring: \(\chi(G)\le\Delta+1\) (greedy); Brooks: \(\chi\le\Delta\) unless complete or odd cycle. Four color theorem: planar \(\chi\le4\). Planarity: Kuratowski — no \(K_5\) or \(K_{3,3}\) subdivision; Wagner — no \(K_5\) or \(K_{3,3}\) minor.
Minors. \(H\) is a minor of \(G\) if \(H\) is obtained by deleting vertices/edges and contracting edges. Graph Minor Theorem (Robertson–Seymour): every minor-closed family has a finite set of forbidden minors. (Existence; the finite list need not be explicit.) Seifert-level one-liner: classical knot/Seifert surface intuition parallels "obstruction by forbidden configurations"; for graphs, Wagner's theorem is the \(K_5,K_{3,3}\) case of the general finite-obstruction phenomenon for minor-closed properties (planarity, bounded treewidth, etc.).
Treewidth \(\mathrm{tw}(G)\): min width of a tree decomposition. Courcelle: MSO properties decidable in linear time on bounded treewidth. Grid minor theorem: large treewidth \(\Rightarrow\) large grid minor.
Spectral: adjacency \(A\), Laplacian \(L=D-A\); algebraic connectivity \(\lambda_2(L)\); expanders via Cheeger inequalities.
See it¶
Max-flow min-cut (Ford–Fulkerson / integral flows): for unit capacities, Menger's edge version is the special case. Algorithmic length of augmenting paths + residual graphs is the constructive content.
Check¶
Why is Hamiltonicity hard while Eulerian is easy?
Euler reduces to degree parity + connectivity (local conditions). Hamilton requires a global simple cycle through all vertices; no known local certificate of the Euler type; decision problem NP-complete.
Is every nonplanar graph a \(K_5\) or \(K_{3,3}\) minor?
Yes for the obstruction characterization (Wagner): nonplanar \(\Leftrightarrow\) contains \(K_5\) or \(K_{3,3}\) as a minor. Kuratowski uses subdivisions (topological minors), equivalent for these two graphs in the planarity case.
Pitfalls¶
- Multigraphs vs simple: Euler, flows, and spectral statements shift.
- Directed graphs: strong connectivity, arborescences (Edmonds), tournaments.
- Minor-closed \(\neq\) subgraph-closed; contractions create edges not present as subgraphs.
Refs¶
Diestel, Graph Theory; Bondy–Murty; Lovász, Combinatorial Problems and Exercises; Robertson–Seymour series (GMM); Mohar–Thomassen (graphs on surfaces).