A sequential development of finite simple graphs that carries one vocabulary - vertices, degrees, adjacency and incidence matrices - from elementary connectivity all the way to spectral analysis. Trees and spanning trees lead to the Laplacian matrix and Kirchhoff's matrix-tree theorem; shortest paths lead to planarity, vertex and edge connectivity, Eulerian and Hamiltonian circuits, dual graphs and Steinitz's theorem; flows on graphs yield max-flow and a proof of Menger's theorem. The same graph is then measured rather than traversed: local centralities (degree, clustering coefficient) and global ones (betweenness, closeness, eccentricity, stress, radiality) alongside diameter, density, global efficiency and the small-world coefficient, with the average and global clustering coefficients kept carefully distinct. Finally the adjacency, Laplacian and normalized Laplacian spectra connect the algebra back to the combinatorics through the Cheeger inequality, and the p-Laplacian generalizes the eigenvalue problem.
Tuzhilin and Zhang's "Introduction to graph theory and basic algorithms" is a book-length set of lecture notes from mathematics courses at Moscow State University and Peking University, written to be…