Proof of the ADE Classification

We prove that a connected simple graph has a finite root system under the mutation game if and only if it is one of the Dynkin diagrams \(A_n\), \(D_n\), \(E_6\), \(E_7\), or \(E_8\).

The spectral criterion

Let \(G\) be a connected simple graph on \(n\) vertices with adjacency matrix \(A\) and Cartan matrix \(C = 2I - A\). As established in Mathematical Background, the root system is finite if and only if \(C\) is positive definite.

Since the eigenvalues of \(C\) are \(2 - \lambda_i\) where \(\lambda_i\) are the eigenvalues of \(A\), positive definiteness of \(C\) is equivalent to:

\[\rho(A) < 2\]

where \(\rho(A)\) denotes the spectral radius (largest eigenvalue) of \(A\). We now classify all connected simple graphs satisfying this condition.

Step 1: The graph must be a tree

Claim. If \(G\) contains a cycle, then \(\rho(A) \geq 2\).

Proof. The cycle graph \(C_m\) on \(m\) vertices has eigenvalues \(2\cos(2\pi k/m)\) for \(k = 0, 1, \ldots, m-1\). The largest eigenvalue is \(2\cos(0) = 2\).

If \(G\) contains \(C_m\) as a subgraph, then by the interlacing theorem for graph spectra, \(\rho(A_G) \geq \rho(A_{C_m}) = 2\).

Therefore \(G\) must be acyclic. Since \(G\) is connected, it is a tree. \(\square\)

Step 2: Maximum degree at most 3

Claim. Every vertex of \(G\) has degree at most 3.

Proof. The star graph \(K_{1,m}\) (one center connected to \(m\) leaves) has adjacency eigenvalues \(\pm\sqrt{m}\) and \(0\) with multiplicity \(m-1\). Thus \(\rho(K_{1,m}) = \sqrt{m}\).

For \(m \geq 4\), we have \(\sqrt{m} \geq 2\). If \(G\) contains a vertex of degree \(\geq 4\), then \(G\) contains \(K_{1,4}\) as a subgraph, and by interlacing \(\rho(A_G) \geq 2\). \(\square\)

Step 3: At most one branch point

Claim. \(G\) has at most one vertex of degree 3 (branch point).

Proof. Suppose \(G\) has two vertices \(u, v\) of degree 3. Since \(G\) is a tree, there is a unique path from \(u\) to \(v\). Each of \(u\) and \(v\) has two additional arms branching off this path. This means \(G\) contains the graph \(T\) formed by two degree-3 vertices connected by a path with an extra leaf at each end:

\[\bullet - u - \cdots - v - \bullet\]

with at least one additional edge at both \(u\) and \(v\). The smallest such graph is:

\[\bullet - \bullet - \bullet - \bullet - \bullet - \bullet\]

(a path of length 5, i.e. \(D_4\) with an extra arm). One can verify directly (or by interlacing with the known \(\tilde{D}_4\) extended Dynkin diagram) that two branch points force \(\rho(A) \geq 2\). \(\square\)

Step 4: No branch point gives A_n

If \(G\) is a tree with no vertex of degree 3, then every vertex has degree at most 2, so \(G\) is a path graph \(A_n\) on \(n\) vertices. Its eigenvalues are \(2\cos\!\bigl(\frac{k\pi}{n+1}\bigr)\) for \(k = 1, \ldots, n\), so:

\[\rho(A_{A_n}) = 2\cos\!\left(\frac{\pi}{n+1}\right) < 2\]

for all \(n \geq 1\). \(\checkmark\)

Step 5: The Diophantine inequality

Suppose \(G\) is a tree with exactly one branch point, having three arms of lengths \(p, q, r\) edges (so \(p + q + r + 1\) vertices total), with \(1 \leq p \leq q \leq r\). We denote this tree \(T_{p,q,r}\).

Theorem. \(\rho(T_{p,q,r}) < 2\) if and only if

(1)\[\frac{1}{p+1} + \frac{1}{q+1} + \frac{1}{r+1} > 1\]

Proof. The argument proceeds in three parts: we establish the characteristic polynomial recurrence for paths, factor the characteristic polynomial of \(T_{p,q,r}\) at its branch point, then evaluate at \(\lambda = 2\).

Part A: Path polynomials are Chebyshev polynomials. Let \(f_\ell(\lambda) = \det(\lambda I - A_{P_\ell})\) be the characteristic polynomial of the path graph on \(\ell\) vertices. By cofactor expansion along the first (or last) row:

\[f_0(\lambda) = 1, \quad f_1(\lambda) = \lambda, \quad f_\ell(\lambda) = \lambda \, f_{\ell-1}(\lambda) - f_{\ell-2}(\lambda)\]

This is exactly the recurrence for the Chebyshev polynomials of the second kind \(U_\ell\) under the substitution \(\lambda = 2\cos\theta\):

\[f_\ell(2\cos\theta) = U_\ell(\cos\theta) = \frac{\sin\bigl((\ell+1)\theta\bigr)}{\sin\theta}\]

In particular, evaluating at \(\lambda = 2\) (i.e. \(\theta \to 0\)):

\[f_\ell(2) = \lim_{\theta \to 0} \frac{\sin\bigl((\ell+1)\theta\bigr)}{\sin\theta} = \ell + 1\]

Part B: Factoring the characteristic polynomial of \(T_{p,q,r}\). The tree \(T_{p,q,r}\) has a central vertex \(v\) of degree 3, connected to three arms which are paths of lengths \(p\), \(q\), \(r\). Expanding \(\det(\lambda I - A)\) along the row and column of \(v\), the three arms decouple:

\[P_{T_{p,q,r}}(\lambda) = \lambda \cdot f_p \cdot f_q \cdot f_r \;-\; f_{p-1} \cdot f_q \cdot f_r \;-\; f_p \cdot f_{q-1} \cdot f_r \;-\; f_p \cdot f_q \cdot f_{r-1}\]

where all polynomials are evaluated at \(\lambda\). The three subtracted terms correspond to the three edges from \(v\) into each arm. Dividing through by \(f_p \cdot f_q \cdot f_r\):

\[\frac{P_{T_{p,q,r}}(\lambda)}{f_p \cdot f_q \cdot f_r} = \lambda - \frac{f_{p-1}}{f_p} - \frac{f_{q-1}}{f_q} - \frac{f_{r-1}}{f_r}\]

So \(\lambda\) is an eigenvalue of \(T_{p,q,r}\) if and only if:

(2)\[\frac{f_{p-1}(\lambda)}{f_p(\lambda)} + \frac{f_{q-1}(\lambda)}{f_q(\lambda)} + \frac{f_{r-1}(\lambda)}{f_r(\lambda)} = \lambda\]

Part C: Evaluating at \(\lambda = 2\). Using \(f_\ell(2) = \ell + 1\) from Part A, the secular equation (2) at \(\lambda = 2\) becomes:

\[\frac{p}{p+1} + \frac{q}{q+1} + \frac{r}{r+1} = 2\]

Rewriting each fraction as \(1 - \frac{1}{\ell+1}\):

\[3 - \left(\frac{1}{p+1} + \frac{1}{q+1} + \frac{1}{r+1}\right) = 2\]

which gives:

\[\frac{1}{p+1} + \frac{1}{q+1} + \frac{1}{r+1} = 1\]

Therefore λ = 2 is an eigenvalue if and only if the sum of reciprocals equals 1. Since the path polynomials \(f_\ell\) are positive and increasing for \(\lambda > 2\cos(\pi/(\ell+1))\), the spectral radius is strictly less than 2 precisely when \(P_{T_{p,q,r}}(2) > 0\), which by the factored form above holds if and only if:

\[\frac{1}{p+1} + \frac{1}{q+1} + \frac{1}{r+1} > 1\]

\(\square\)

Step 6: Enumerating solutions

We now enumerate all integer solutions of (1) with \(1 \leq p \leq q \leq r\).

Case \(p = 1\):

\[\frac{1}{2} + \frac{1}{q+1} + \frac{1}{r+1} > 1 \quad\Longleftrightarrow\quad \frac{1}{q+1} + \frac{1}{r+1} > \frac{1}{2}\]

• \(q = 1\): \(\frac{1}{2} + \frac{1}{r+1} > \frac{1}{2}\) holds for all \(r \geq 1\). This gives \(T_{1,1,r} = D_{r+3}\) for \(r \geq 1\), i.e. \(D_n\) for \(n \geq 4\). \(\checkmark\)

• \(q = 2\): \(\frac{1}{3} + \frac{1}{r+1} > \frac{1}{2}\), so \(r+1 < 6\), i.e. \(r \in \{2, 3, 4\}\):

  • \(T_{1,2,2}\): \(\frac{1}{2} + \frac{1}{3} + \frac{1}{3} = \frac{7}{6} > 1\) → E₆ \(\checkmark\)

  • \(T_{1,2,3}\): \(\frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{13}{12} > 1\) → E₇ \(\checkmark\)

  • \(T_{1,2,4}\): \(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} = \frac{31}{30} > 1\) → E₈ \(\checkmark\)

  • \(T_{1,2,5}\): \(\frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1\) → fails (affine \(\tilde{E}_8\))

• \(q \geq 3\): \(\frac{1}{q+1} + \frac{1}{r+1} \leq \frac{1}{4} + \frac{1}{4} = \frac{1}{2}\), which does not satisfy \(> \frac{1}{2}\). No solutions.

Case \(p = 2\):

\[\frac{1}{3} + \frac{1}{q+1} + \frac{1}{r+1} > 1 \quad\Longleftrightarrow\quad \frac{1}{q+1} + \frac{1}{r+1} > \frac{2}{3}\]

Since \(q \geq p = 2\), we have \(\frac{1}{q+1} \leq \frac{1}{3}\), so \(\frac{1}{r+1} > \frac{1}{3}\), requiring \(r < 2\). But \(r \geq q \geq 2\), a contradiction. No solutions.

Case \(p \geq 3\): Then \(\frac{1}{p+1} + \frac{1}{q+1} + \frac{1}{r+1} \leq 3 \cdot \frac{1}{4} < 1\). No solutions.

The complete classification

Combining all steps, the connected simple graphs with \(\rho(A) < 2\) are exactly:

Diagram	Tree structure	Diophantine data
\(A_n\) (\(n \geq 1\))	Path on \(n\) vertices	(no branch point)
\(D_n\) (\(n \geq 4\))	\(T_{1, 1, n-3}\)	\(\frac{1}{2} + \frac{1}{2} + \frac{1}{n-2} > 1\)
\(E_6\)	\(T_{1, 2, 2}\)	\(\frac{1}{2} + \frac{1}{3} + \frac{1}{3} > 1\)
\(E_7\)	\(T_{1, 2, 3}\)	\(\frac{1}{2} + \frac{1}{3} + \frac{1}{4} > 1\)
\(E_8\)	\(T_{1, 2, 4}\)	\(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} > 1\)

No other connected simple graphs produce a finite root system under the mutation game. \(\blacksquare\)

Connections

The inequality \(\frac{1}{p+1} + \frac{1}{q+1} + \frac{1}{r+1} > 1\) is the same constraint that classifies:

• Platonic solids — via Euler’s formula \(V - E + F = 2\) applied to regular polyhedra with face valence \(p+1\), vertex valence \(q+1\)

• Finite subgroups of SO(3) — cyclic, dihedral, tetrahedral (E₆), octahedral (E₇), icosahedral (E₈)

• Finite subgroups of SU(2) — the binary polyhedral groups (McKay correspondence)

• Spherical triangle groups — triangles with angles \(\frac{\pi}{p+1}, \frac{\pi}{q+1}, \frac{\pi}{r+1}\) on the sphere (angle sum > π)

• Simple singularities — Arnold’s classification of ADE singularities (the low-codimension cases are Thom’s seven catastrophes)

This ubiquity was highlighted by V. I. Arnold [Arnold1976] and is one of the most striking phenomena in mathematics.

References

[Arnold1976]

V. I. Arnold, “Problems in present day mathematics,” in Mathematical Developments Arising from Hilbert Problems, Proceedings of Symposia in Pure Mathematics, vol. 28, AMS, 1976.