Search & glossary

Every rule and concept in Graph Theory, with its definition and a link to the lesson that teaches it. Search by term, by idea, or by lesson title.

Glossary (54)

Bipartite graphs and the odd-cycle theorem: A graph $G = (V, E)$ is bipartite if $V$ splits into two parts $X$ and $Y$ with every edge joining $X$ to $Y$ — no edge lies inside $X$ or inside $Y$ .; Bipartite Graphs and Matchings › Bipartite Graphs and Odd Cycles
Cayley's Formula and the Prufer code: The number of labeled trees on vertex set $\{1, \ldots, n\}$ (equivalently, the number of spanning trees of $K_n$ ) is $n^{n-2}$ for $n \ge 2$ — Cayleys Formula.; Trees › Cayley's Formula and Prufer Codes
Connected components: Vertices $u$ and $v$ are connected if some walk joins them.; Walks, Paths and Connectivity › Connected Components
Connectivity and Menger's theorem: The vertex connectivity $\kappa(G)$ is the smallest number of vertices whose removal disconnects $G$ (or leaves a single vertex); the edge connectivity $\lambda(G)$ is the smallest number of edges whose removal disconnects $G$ .; Walks, Paths and Connectivity › Connectivity and Menger's Theorem
Counting walks with a matrix: If $A$ is the adjacency matrix of $G$ (Topic 1), with rows and columns indexed by $V(G)$ , then for every $k \ge 1$ the entry $(A^k)_{ij}$ equals the number of walks of length $k$ from $i$ to $j$ .; Walks, Paths and Connectivity › Counting Walks with Matrix Powers
Cut vertices and bridges: A vertex $v$ of a connected graph $G$ is a cut vertex if $G - v$ — delete $v$ and every edge at $v$ — is disconnected.; Walks, Paths and Connectivity › Cut Vertices and Bridges
Cuts and the max-flow min-cut theorem: An $s$ - $t$ cut is a partition $V = S \sqcup T$ with $s \in S$ , $t \in T$ .; Directed Graphs and Network Flows › The Max-Flow Min-Cut Theorem
DAGs and topological order: A directed acyclic graph (DAG) is a directed graph with no directed cycle.; Graph Algorithms › Directed Acyclic Graphs and Topological Order
Degree and the handshake lemma: The degree of vertex $v$ , written $\deg(v)$ , is the number of edges incident to $v$ (equivalently, the number of neighbors of $v$ ).; Graphs and Degrees › Degree and the Handshake Lemma
Degree sequences and the Havel-Hakimi test: The degree sequence of $G$ lists $\deg(v)$ for every vertex, usually sorted $d_1 \ge d_2 \ge \cdots \ge d_n$ .; Graphs and Degrees › Degree Sequences
Digraphs, arcs, in-degree and out-degree: A directed graph (digraph) $D = (V, A)$ has a vertex set $V$ and a set $A$ of arcs, each an ORDERED pair $(u,v)$ with $u \ne v$ , also written $u \to v$ .; Directed Graphs and Network Flows › Directed Graphs and Tournaments
Dijkstra's algorithm: Dijkstra's algorithm finds shortest-path distances from a source $s$ in a graph with non-negative edge weights.; Graph Algorithms › Shortest Paths: Dijkstra's Algorithm
Edge coloring and the chromatic index: A proper edge coloring assigns colors to the edges of $G$ so that any two edges sharing a vertex get DIFFERENT colors.; Graph Coloring › Edge Coloring
Euler circuits and Euler trails: A walk that uses every edge of a graph exactly once is an Euler trail; if it starts and ends at the same vertex, it is an Euler circuit.; Eulerian and Hamiltonian Graphs › Eulerian Circuits and Trails
Euler's Formula for plane graphs: For any connected plane graph with $V$ vertices, $E$ edges and $F$ faces (counting the outer face), $ $V - E + F = 2.$ $; Planar Graphs › Euler's Formula
Euler's original question: The city of Königsberg had two river banks ( $A$ , $B$ ) and two islands ( $C$ , $D$ ), joined by seven bridges: two between $A$ and $C$ , two between $B$ and $C$ , and one each for $A$ – $D$ , $B$ – $D$ , $C$ – $D$ .; Eulerian and Hamiltonian Graphs › The Bridges of Konigsberg
Flow networks, flows and value: A flow network is a digraph $D$ with a nonnegative capacity $c(u,v)$ on every arc, a source $s$ (no arcs enter it) and a sink $t$ (no arcs leave it).; Directed Graphs and Network Flows › Networks and Flows
Forbidding a bigger clique: the Turán graph: For $r \ge 2$ , the Turán graph $T(n,r)$ is the complete $r$ -partite graph on $n$ vertices whose parts are as equal as possible (sizes $\lceil n/r\rceil$ or $\lfloor n/r\rfloor$ ).; Extremal Graph Theory and Ramsey Theory › Turán's Theorem
Graph invariant: A graph invariant is any quantity computed from a graph that is equal for isomorphic graphs — $|V|$ , $|E|$ , the degree sequence, the number of connected components, and the number of triangles are all invariants.; Isomorphism and Subgraphs › Invariants That Tell Graphs Apart
Gray codes as Hamiltonian cycles: A (cyclic) Gray code on $n$ bits lists all $2^n$ bit-strings so that consecutive strings — including the last back to the first — differ in exactly one bit.; Eulerian and Hamiltonian Graphs › Gray Codes and Tours
Greedy coloring and Brooks' theorem: Fix an order $v_1,\ldots,v_n$ of $V$ .; Graph Coloring › Greedy Coloring and Brooks' Theorem
Hall's condition: For a bipartite graph with parts $X, Y$ , write $N(S)$ for the set of all neighbors (in $Y$ ) of a subset $S \subseteq X$ .; Bipartite Graphs and Matchings › Hall's Marriage Theorem
Hamiltonian cycles and paths: A Hamiltonian cycle visits every vertex of a graph exactly once and returns to its start; a Hamiltonian path visits every vertex exactly once without returning.; Eulerian and Hamiltonian Graphs › Hamiltonian Cycles
Isomorphism: Graphs $G$ and $H$ are isomorphic, written $G \cong H$ , if there is a bijection $\varphi: V(G) \to V(H)$ such that $uv \in E(G) \iff \varphi(u)\varphi(v) \in E(H)$ for all $u, v$ .; Isomorphism and Subgraphs › Graph Isomorphism
Kirchhoff's theorem: The Laplacian of a graph $G$ on $n$ vertices is $L = D - A$ , where $D$ is the diagonal matrix of degrees and $A$ is the adjacency matrix.; Trees › The Matrix-Tree Theorem
Kruskal's and Prim's algorithms: A minimum spanning tree (MST) of a connected weighted graph is a spanning tree (Topic 4) whose edge weights sum to the least total possible.; Graph Algorithms › Minimum Spanning Trees: Kruskal and Prim
Labeled vs. unlabeled counts: A simple graph on labeled vertices $\{1,\ldots,n\}$ is exactly a choice of which of the $\binom n2$ possible edges to include, so there are $2^{\binom n2}$ labeled graphs on $n$ vertices.; Isomorphism and Subgraphs › Counting Graphs
Matchings, maximal and maximum: A matching $M \subseteq E$ is a set of edges no two of which share a vertex.; Bipartite Graphs and Matchings › Matchings
Planar graphs, plane drawings, and faces: A graph is planar if it has at least one drawing in the plane with no two edges crossing, except where they share an endpoint.; Planar Graphs › Planar Graphs and Plane Drawings
Polyhedra, duals, and self-duality: The graph of a convex polyhedron — one vertex per corner, one edge per edge of the solid — has a plane drawing (a Schlegel diagram), so Euler's Formula applies directly to $V$ , $E$ , $F$ of the SOLID.; Planar Graphs › Polyhedra and Dual Graphs
Proper coloring and chromatic number: A proper $k$ -coloring of $G=(V,E)$ assigns one of $k$ colors to each vertex so that every edge joins two DIFFERENT colors.; Graph Coloring › Vertex Coloring and Chromatic Number
Ramsey numbers: Color every edge of the complete graph $K_n$ either red or blue.; Extremal Graph Theory and Ramsey Theory › Ramsey Numbers and $R(3,3)=6$
Residual graphs and the Ford-Fulkerson method: Given a flow $f$ , the residual graph $D_f$ has, for every arc $(u,v)$ with $f(u,v) < c(u,v)$ , a FORWARD residual arc $u \to v$ of capacity $c(u,v)-f(u,v)$ ; and for every arc with $f(u,v) > 0$ , a BACKWARD residual arc $v \to u$ of capacity $f(u,v)$ , which un…; Directed Graphs and Network Flows › Augmenting Paths
Self-complementary: A graph $G$ on $n$ vertices is self-complementary if $G \cong \overline G$ .; Isomorphism and Subgraphs › Self-Complementary Graphs
Six families worth naming: $K_n$ (complete graph): every pair of its $n$ vertices is adjacent; $|E| = \binom{n}{2}$ and every vertex has degree $n-1$ .; Graphs and Degrees › A Catalog of Special Graphs
Spanning trees and circuit rank: A spanning tree of a connected graph $G$ is a subgraph that is a tree and includes every vertex of $G$ .; Trees › Spanning Trees
Stability and the Gale-Shapley algorithm: Given two equal-size sets, say men and women, each person ranks every member of the other set.; Bipartite Graphs and Matchings › Stable Matchings
Strong connectivity and strongly connected components: Vertices $u,v$ of a digraph $D$ are mutually reachable if $D$ has a directed $u\to v$ path AND a directed $v \to u$ path.; Directed Graphs and Network Flows › Strong Connectivity
Subdivisions and Kuratowski's Theorem: A subdivision of a graph $H$ replaces some of its edges by paths through new degree- $2$ vertices, without otherwise changing adjacency.; Planar Graphs › K_5, K_3,3 and Kuratowski's Theorem
Subgraph, induced subgraph, complement: A graph $H$ is a subgraph of $G$ , written $H\subseteq G$ , if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$ .; Isomorphism and Subgraphs › Subgraphs and Complements
Sufficient conditions for a Hamiltonian cycle: Dirac's theorem: if a graph has $n \ge 3$ vertices and every vertex has degree $\ge n/2$ , it has a Hamiltonian cycle.; Eulerian and Hamiltonian Graphs › Dirac's and Ore's Theorems
The adjacency matrix: For $G=(V,E)$ with $V=\{v_1,\ldots,v_n\}$ , the adjacency matrix $A$ is the $n\times n$ matrix with $A_{ij} = 1$ if $\{v_i,v_j\}\in E$ and $A_{ij}=0$ otherwise (so $A_{ii}=0$ for a simple graph).; Graphs and Degrees › Adjacency Matrices
The chromatic polynomial and deletion-contraction: The chromatic polynomial $P(G,k)$ counts the proper colorings of $G$ using (up to) $k$ available colors.; Graph Coloring › The Chromatic Polynomial
The edge-count bounds: If a simple connected planar graph has $V \ge 3$ vertices, then $ $E \le 3V - 6,$ $ with equality only for triangulations (every face a triangle).; Planar Graphs › Edge Bounds for Planar Graphs
The Erdős–Szekeres recursion: For $s,t\ge2$ , $ $R(s,t) \le R(s-1,t) + R(s,t-1),$ $with base cases$ R(s,2)=s $and$ R(2,t)=t $for all$ s,t≥2$.; Extremal Graph Theory and Ramsey Theory › Bounds on Ramsey Numbers
The first moment method: To prove some object with a property exists, it suffices to build a RANDOM object and show the expected number of "bad" events is less than $1$ — since a random variable that is always a non-negative integer and averages below $1$ must sometimes equal $0$ .; Extremal Graph Theory and Ramsey Theory › The Probabilistic Method
The Five and Four Color Theorems: Every planar graph satisfies $\chi(G) \le 5$ (the Five Color Theorem, proved in full below) and, in fact, $\chi(G) \le 4$ (the Four Color Theorem).; Graph Coloring › The Five and Four Color Theorems
The handshake for trees, and two leaves: A tree $T$ with $n \ge 2$ vertices has $n - 1$ edges, so by the handshake lemma $\sum_v \deg(v) = 2(n - 1)$ .; Trees › Leaves and Edge Counts
Tree: four faces of one idea: A graph $T$ on $n$ vertices is a tree if it is connected and has no cycles.; Trees › What Makes a Tree
Triangle-free graphs and the $n^2/4$ bound: The Turán number $\operatorname{ex}(n, K_3)$ is the maximum number of edges a triangle-free graph on $n$ vertices can have.; Extremal Graph Theory and Ramsey Theory › Mantel's Theorem
Two ways to explore a graph: Breadth-first search (BFS) from a vertex $s$ visits vertices in order of their distance from $s$ : it keeps a queue, starts with $s$ at distance $0$ , and whenever it dequeues a vertex $u$ it enqueues every unvisited neighbor of $u$ at distance $d(u) + 1$ .; Graph Algorithms › Breadth-First and Depth-First Search
Vertex covers and Konig's theorem: A vertex cover is a set $C \subseteq V$ touching every edge (each edge has at least one endpoint in $C$ ).; Bipartite Graphs and Matchings › Konig's Theorem and Vertex Covers
Vertices, edges, order and size: A (simple) graph $G = (V, E)$ consists of a finite set $V$ of vertices together with a set $E$ of edges, each edge an unordered pair $\{u, v\}$ of distinct vertices.; Graphs and Degrees › What Is a Graph?
Walks, trails, paths and cycles: A walk is a sequence $v_0, e_1, v_1, e_2, \ldots, e_k, v_k$ with each $e_i$ the edge $v_{i-1}v_i$ ; its length is the number $k$ of edges.; Walks, Paths and Connectivity › Walks, Trails, Paths and Cycles