If folks are looking for terms to Google, try "spectral graph theory" and "algebraic graph theory"<p><a href="https://en.wikipedia.org/wiki/Spectral_graph_theory" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Spectral_graph_theory</a><p><a href="https://en.wikipedia.org/wiki/Algebraic_graph_theory" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Algebraic_graph_theory</a><p>Pretty much every field in math has a related field where you try to turn problems from the former into linear algebra problems.<p>The "spectral theorem" (<a href="https://en.wikipedia.org/wiki/Spectral_theorem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Spectral_theorem</a>) is an important theorem in linear algebra that gives conditions for when a matrix can be diagonalized, which is closely related to what its eigenvalues/eigenvectors look like.<p>The simplest version of the spectral theorem says that a symmetric matrix with real-number entries has real-number eigenvalues. The eigenvalues of a matrix are called the "spectrum of the matrix", hence "spectral theorem" and "spectral graph theory".<p>The adjacency matrix of any undirected graph is real symmetric, so its eigenvalues are all real numbers and it's natural to ask whether they say anything about the underlying graph.<p>Lucky for us, there are lots of surprising connections!<p>For example, say G is an finite undirected graph. The chromatic number of G, denoted χ(G), is the fewest number of colors needed to color its vertexes so that no two adjacent vertexes have the same color.<p>If λ₁ is the largest eigenvalue of G's adjacency matrix then there's a theorem (Wilf's theorem) that says<p><pre><code> χ(G) ≤ 1 + ⌊λ₁⌋
</code></pre>
That is, you can always color a graph with 1 + ⌊λ₁⌋ colors, where ⌊x⌋ is the floor of x.<p>And there are some (finite, undirected) graphs that require exactly 1 + ⌊λ₁⌋ colors, so we're not doing any better unless we can say something more specific about the graph.<p>Wilf's Theorem:<p><a href="https://www2.math.upenn.edu/~wilf/website/Eigenvalues%20of%20a%20graph.pdf" rel="nofollow noreferrer">https://www2.math.upenn.edu/~wilf/website/Eigenvalues%20of%2...</a><p><a href="https://www2.math.upenn.edu/~wilf/website/Inequality%20for%20Chromatic%20Number.pdf" rel="nofollow noreferrer">https://www2.math.upenn.edu/~wilf/website/Inequality%20for%2...</a>