Six degrees of Kevin Bacon, Paul Erdos, and Wikipedia johndcook.com/blog/2018/12/0…

A simple graph is an undirected graph with no edges from a vertex to itself and no more than one edge between different vertices.

The degree matrix of a graph is a diagonal matrix whose ii-th entry is the degree of the ith node.

The Laplacian matrix of a simple graph is L = D - A where D is the degree matrix and A is the adjacency matrix.

Normalized Laplacian: L_n = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}

Wagner’s theorem en.wikipedia.org/wiki/Wagner%27…

The eigenvalues of the graph Laplacian matrix can tell you whether a graph is connected. They can also tell you how well a connected graph is connected. johndcook.com/blog/2016/01/0…

Using the pseudoinverse of a matrix to compute effective graph resistance johndcook.com/blog/2025/05/2…

Applications of graphs cs.stackexchange.com/questions/1261…

The smallest eigenvalue of the graph Laplacian is always 0. The corresponding eigenvector contains all 1's.

The number of zero eigenvalues of the graph Laplacian equals the number of components of its graph.

The eigenvalues of the graph Laplacian are denoted λ_1, λ_2, ... in non-decreasing order, not necessarily distinct.

Expected time for a random walk to visit every node in a graph johndcook.com/blog/2017/01/0…

Network analysis of Game of Thrones qz.com/650796

If λ_2, the second eigenvalue of the graph Laplacian, is positive the graph is connected.

λ_2 is called the algebraic connectivity of a graph, sometimes also called the spectral gap.

Roughly speaking, category theory is graph theory with additional structure to represent composition.

Eigenvalues of random power law graphs math.ucsd.edu/~fan/wp/eigen.…

An articulation point is a vertex whose removal disconnects a graph. A bridge is an edge whose removal disconnects a graph.

Prim's algorithm for finding minimum spanning trees requires O(E + V log V) time.