Graph Theory
Hierarchical Navigable Small World (HNSW)
A graph-based index for approximate nearest-neighbour search that descends a stack of navigable small-world graphs in logarithmic time.
Handshake Lemma
The sum of all vertex degrees in a finite graph equals twice the number of edges.
Euler's Formula for Planar Graphs
For any connected planar graph, V − E + F = 2, where F counts the faces including the outer face.
Hall's Marriage Theorem
A bipartite graph has a perfect matching from X to Y iff every subset of X has at least as many neighbors in Y.
König's Theorem (Bipartite)
In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Menger's Theorem
The maximum number of internally vertex-disjoint paths between two vertices equals the minimum vertex cut separating them.
Dilworth's Theorem
In any finite partially ordered set, the minimum number of chains needed to cover the poset equals the maximum size of an antichain.
Cayley's Formula (nⁿ⁻² trees)
The number of labeled spanning trees on n vertices is nⁿ⁻², proved by Prüfer sequences.
Matrix-Tree Theorem
The number of spanning trees of a graph equals any cofactor of its Laplacian matrix.