[proofplan] We translate the finite simply laced condition into positive definiteness of the symmetric Cartan matrix $C_\Gamma$. Positive definiteness first excludes cycles and high-valence vertices, so $\Gamma$ is a tree whose vertices have degree at most $3$. If there is no degree-$3$ vertex, the tree is a path and hence is $A_\ell$; if there is a degree-$3$ vertex, positive definiteness excludes a second branch point and then a determinant computation for a three-armed tree gives the inequality $\frac1p+\frac1q+\frac1r>1$. Solving this elementary inequality gives exactly the $D$ and $E$ diagrams, and the converse is supplied by the standard coordinate root systems for types $A$, $D$, and $E$. [/proofplan] [step:Express positive definiteness through the graph quadratic form] Let $V$ be the finite vertex set of $\Gamma$. For a function \begin{align*} x: V &\to \mathbb{R}\\ v &\mapsto x_v, \end{align*} define the quadratic form $Q_\Gamma: \mathbb{R}^V \to \mathbb{R}$ by \begin{align*} Q_\Gamma(x) = \sum_{v,w \in V} (C_\Gamma)_{vw} x_v x_w. \end{align*} Since $C_\Gamma$ is symmetric, the hypothesis says that $Q_\Gamma(x)>0$ for every nonzero $x \in \mathbb{R}^V$. Expanding the entries of $C_\Gamma$ gives \begin{align*} Q_\Gamma(x) = 2\sum_{v \in V} x_v^2 - 2\sum_{\{v,w\} \in E(\Gamma)} x_v x_w, \end{align*} where $E(\Gamma)$ is the set of unordered edges of $\Gamma$. If $\Gamma'$ is an induced subgraph of $\Gamma$ with vertex set $V' \subset V$, then $C_{\Gamma'}$ is the principal submatrix of $C_\Gamma$ indexed by $V'$. Hence $C_{\Gamma'}$ is positive definite, because every principal submatrix of a positive definite real symmetric matrix is positive definite. We shall use this repeatedly to rule out forbidden induced subgraphs. [guided] The graph determines the matrix completely in the simply laced case: diagonal entries are $2$, adjacent vertices contribute $-1$, and non-adjacent distinct vertices contribute $0$. Thus a vector $x \in \mathbb{R}^V$ is the same thing as assigning a real number $x_v$ to each vertex $v$ of the graph, and the matrix condition becomes the positivity of the quadratic form \begin{align*} Q_\Gamma(x) = \sum_{v,w \in V} (C_\Gamma)_{vw}x_vx_w = 2\sum_{v \in V} x_v^2 - 2\sum_{\{v,w\} \in E(\Gamma)} x_vx_w. \end{align*} The factor $2$ in the edge term appears because the symmetric matrix contains both entries $(C_\Gamma)_{vw}$ and $(C_\Gamma)_{wv}$ for an unordered edge $\{v,w\}$. We also need a heredity observation. If $\Gamma'$ is an induced subgraph with vertex set $V'$, then the matrix $C_{\Gamma'}$ is exactly the principal submatrix of $C_\Gamma$ obtained by restricting to rows and columns in $V'$. If $y \in \mathbb{R}^{V'}$ is nonzero, extend it to $x \in \mathbb{R}^V$ by setting $x_v=y_v$ for $v \in V'$ and $x_v=0$ for $v \notin V'$. Then \begin{align*} y^\top C_{\Gamma'}y = x^\top C_\Gamma x > 0. \end{align*} Therefore every induced subgraph of $\Gamma$ also has positive definite Cartan matrix. This lets us disprove possible shapes by finding one nonzero vector on a smaller subgraph for which the quadratic form is non-positive. [/guided] [/step] [step:Exclude cycles and vertices of degree at least four] Suppose first that $\Gamma$ contains a cycle with distinct vertices $v_1,\dots,v_m$, where $m \ge 3$, and edges $\{v_i,v_{i+1}\}$ for $1 \le i<m$ and $\{v_m,v_1\}$. Let $\Gamma'$ be the induced subgraph on these cycle vertices, and define $x \in \mathbb{R}^{V(\Gamma')}$ by $x_{v_i}=1$ for every $i$. The cycle edges alone contribute $m$ edges, and any additional edges in the induced subgraph contribute non-positive terms. In particular, for the cycle subgraph itself one has \begin{align*} 2\sum_{i=1}^m x_{v_i}^2 - 2\sum_{i=1}^m x_{v_i}x_{v_{i+1}} = 2m - 2m = 0, \end{align*} where $v_{m+1}=v_1$. Thus the cycle subgraph has a nonzero vector of quadratic value $0$, contradicting positive definiteness of the corresponding principal submatrix. Hence $\Gamma$ has no cycle. Now suppose that a vertex $v_0$ has four distinct neighbours $v_1,v_2,v_3,v_4$. Let $\Gamma''$ be the induced subgraph on $\{v_0,v_1,v_2,v_3,v_4\}$, and define $x \in \mathbb{R}^{V(\Gamma'')}$ by \begin{align*} x_{v_0}=2,\qquad x_{v_i}=1 \quad \text{for } 1 \le i \le 4. \end{align*} Since $\Gamma$ has no cycles, no two of $v_1,\dots,v_4$ are adjacent. Therefore \begin{align*} Q_{\Gamma''}(x) &= 2\left(2^2+\sum_{i=1}^4 1^2\right)-2\sum_{i=1}^4 2\cdot 1\\ &=2(4+4)-16\\ &=0. \end{align*} This again contradicts positive definiteness. Therefore every vertex of $\Gamma$ has degree at most $3$. [guided] A positive definite simply laced diagram cannot contain a cycle. To see the obstruction, take a cycle with vertices $v_1,\dots,v_m$, where $m \ge 3$, and put the same value $1$ on every vertex of the cycle. On the cycle subgraph, the diagonal contribution is \begin{align*} 2\sum_{i=1}^m 1^2 = 2m, \end{align*} while the edge contribution is \begin{align*} 2\sum_{i=1}^m 1\cdot 1 = 2m. \end{align*} Thus the quadratic form has value $0$ on a nonzero vector. A positive definite matrix cannot have such a vector. Since positive definiteness passes to principal submatrices, this excludes cycles inside $\Gamma$. Next we rule out degree at least $4$. Suppose $v_0$ has four distinct neighbours $v_1,v_2,v_3,v_4$. Because we have already excluded cycles, two of these neighbours cannot be adjacent: if $v_i$ and $v_j$ were adjacent, then $v_i-v_0-v_j-v_i$ would form a cycle. Now assign value $2$ to the central vertex and value $1$ to the four neighbours: \begin{align*} x_{v_0}=2,\qquad x_{v_i}=1 \quad \text{for } 1 \le i \le 4. \end{align*} The quadratic form on this five-vertex induced subgraph is \begin{align*} Q_{\Gamma''}(x) &= 2\left(2^2+\sum_{i=1}^4 1^2\right)-2\sum_{i=1}^4 2\cdot 1\\ &= 2(4+4)-16\\ &=0. \end{align*} Again this contradicts positive definiteness. Hence every vertex has degree at most $3$. [/guided] [/step] [step:Reduce the classification to paths and three armed trees] Since $\Gamma$ is connected and has no cycles, it is a tree. Since every vertex has degree at most $3$, either every vertex has degree at most $2$, or there is a vertex of degree $3$. If every vertex has degree at most $2$, then a finite connected tree with maximum degree $2$ is a path. A path with $\ell$ vertices is the Dynkin diagram $A_\ell$. It remains to consider the case where $\Gamma$ has a vertex of degree $3$. We first show that there can be only one such vertex. Suppose there are two distinct degree-$3$ vertices $a$ and $b$. Since $\Gamma$ is a tree, there is a unique simple path from $a$ to $b$; let this path have $m \ge 1$ edges. Choose two neighbours of $a$ not lying on this path and two neighbours of $b$ not lying on this path. Let $\Gamma'$ be the induced subgraph consisting of the path from $a$ to $b$ together with these four extra adjacent vertices. Define $x \in \mathbb{R}^{V(\Gamma')}$ by assigning value $2$ to every vertex on the path from $a$ to $b$ and value $1$ to each of the four extra vertices. The path contains $m+1$ vertices and $m$ edges, and there are four extra edges from the branch vertices to the extra vertices. Hence \begin{align*} Q_{\Gamma'}(x) &=2\left(4(m+1)+4\right)-2\left(4m+4\cdot 2\right)\\ &=8m+16-8m-16\\ &=0. \end{align*} This contradicts positive definiteness. Thus $\Gamma$ has exactly one degree-$3$ vertex in the branching case. Therefore every branching diagram is a three-armed tree: there is a unique branch vertex $b$, and deleting $b$ leaves three path components. Let $p,q,r$ be the numbers of vertices in the three paths from $b$ to the corresponding terminal vertices, counted including $b$. Reorder them so that \begin{align*} 2 \le p \le q \le r. \end{align*} [guided] Once cycles are excluded, connectedness says that $\Gamma$ is a tree. A finite connected tree in which all degrees are at most $2$ must be a path: starting at one endpoint and walking along the unique unused edge lists all vertices in a single chain. Therefore this case gives exactly $A_\ell$, where $\ell$ is the number of vertices. Now assume that some vertex has degree $3$. We need to know whether there can be more than one branch point. Suppose two distinct degree-$3$ vertices exist; call them $a$ and $b$. Since the graph is a tree, there is exactly one simple path from $a$ to $b$. Let this path have $m$ edges, so it has $m+1$ vertices. At $a$, one edge lies on the path toward $b$, so there are two other incident edges. At $b$, similarly, there are two other incident edges. Keep just the path and these four additional neighbouring vertices. Now put value $2$ on every vertex of the path from $a$ to $b$ and value $1$ on the four extra leaves. The diagonal part of the quadratic form is \begin{align*} 2\left(4(m+1)+4\right), \end{align*} because there are $m+1$ path vertices with square $4$ and four extra vertices with square $1$. The edge part consists of $m$ path edges, each with product $2\cdot2=4$, and four leaf edges, each with product $2\cdot1=2$. Therefore \begin{align*} Q_{\Gamma'}(x) &=2\left(4(m+1)+4\right)-2\left(4m+4\cdot 2\right)\\ &=0. \end{align*} This nonzero vector contradicts positive definiteness. Hence a finite simply laced positive definite connected diagram has at most one branch point. So the branching case has a single central vertex $b$ of degree $3$. Removing $b$ leaves three disjoint paths. We encode their lengths by integers $p,q,r$, where each number counts the vertices in the corresponding arm including the common branch vertex $b$. Thus each of $p,q,r$ is at least $2$, and after reordering we may assume \begin{align*} 2 \le p \le q \le r. \end{align*} [/guided] [/step] [step:Compute the determinant of a three armed tree] Let $T_{p,q,r}$ denote the three-armed tree with one branch vertex and arms of vertex-lengths $p,q,r$ counted including the branch vertex. We compute the determinant of its Cartan matrix. For $n \ge 1$, let $A_n$ denote the path on $n$ vertices, and let $C_{A_n}$ be its Cartan matrix. Define $d_n=\det C_{A_n}$, with the convention $d_0=1$. Expanding the tridiagonal determinant along the last row gives \begin{align*} d_n = 2d_{n-1}-d_{n-2} \quad \text{for } n \ge 2, \end{align*} with $d_0=1$ and $d_1=2$. Hence $d_n=n+1$ for all $n \ge 0$. Order the vertices of $T_{p,q,r}$ so that the branch vertex comes first and the three arms without the branch vertex follow. The block corresponding to the three deleted arms is \begin{align*} B = C_{A_{p-1}} \oplus C_{A_{q-1}} \oplus C_{A_{r-1}}. \end{align*} The branch vertex has diagonal entry $2$ and is adjacent to the first vertex in each arm. By the Schur complement formula, \begin{align*} \det C_{T_{p,q,r}} = \det(B)\left(2-u^\top B^{-1}u\right), \end{align*} where $u$ is the column vector whose nonzero entries are $-1$ in the first coordinate of each arm block. For the path matrix $C_{A_n}$, [Cramer's rule](/theorems/3305) gives \begin{align*} (C_{A_n}^{-1})_{11}=\frac{\det C_{A_{n-1}}}{\det C_{A_n}}=\frac{n}{n+1}. \end{align*} Applying this with $n=p-1,q-1,r-1$, we obtain \begin{align*} u^\top B^{-1}u = \frac{p-1}{p}+\frac{q-1}{q}+\frac{r-1}{r}. \end{align*} Also \begin{align*} \det(B)=pqr. \end{align*} Therefore \begin{align*} \det C_{T_{p,q,r}} &=pqr\left(2-\frac{p-1}{p}-\frac{q-1}{q}-\frac{r-1}{r}\right)\\ &=pqr\left(\frac1p+\frac1q+\frac1r-1\right). \end{align*} Since $C_{T_{p,q,r}}$ is positive definite, its determinant is positive. Hence \begin{align*} \frac1p+\frac1q+\frac1r>1. \end{align*} [guided] The classification now depends on a numerical restriction on the three arm lengths. Let $T_{p,q,r}$ be the three-armed tree with arm lengths $p,q,r$, counted including the common branch vertex. We compute the determinant of its Cartan matrix and use the fact that a positive definite matrix has positive determinant. First consider a path $A_n$ with $n$ vertices. Its Cartan matrix is tridiagonal, with diagonal entries $2$ and adjacent off-diagonal entries $-1$. Let \begin{align*} d_n=\det C_{A_n}, \qquad d_0=1. \end{align*} Expanding the tridiagonal determinant along the last row gives \begin{align*} d_n=2d_{n-1}-d_{n-2} \quad \text{for } n \ge 2, \end{align*} with $d_1=2$. The sequence $d_n=n+1$ satisfies the same recurrence and the same initial conditions, so \begin{align*} \det C_{A_n}=n+1. \end{align*} Now remove the branch vertex from $T_{p,q,r}$. The remaining graph is the disjoint union of three paths with $p-1$, $q-1$, and $r-1$ vertices. Thus the corresponding block of the Cartan matrix is \begin{align*} B=C_{A_{p-1}}\oplus C_{A_{q-1}}\oplus C_{A_{r-1}}. \end{align*} The branch vertex contributes a scalar diagonal block $2$. It is connected to the first vertex in each arm, so the off-diagonal vector $u$ has exactly three nonzero entries, each equal to $-1$, one in the first coordinate of each path block. The Schur complement formula gives \begin{align*} \det C_{T_{p,q,r}} = \det(B)\left(2-u^\top B^{-1}u\right). \end{align*} We need the first diagonal entry of the inverse of a path Cartan matrix. By Cramer's rule, deleting the first row and first column of $C_{A_n}$ leaves $C_{A_{n-1}}$, so \begin{align*} (C_{A_n}^{-1})_{11} =\frac{\det C_{A_{n-1}}}{\det C_{A_n}} =\frac{n}{n+1}. \end{align*} Using this for the three arm blocks gives \begin{align*} u^\top B^{-1}u = \frac{p-1}{p}+\frac{q-1}{q}+\frac{r-1}{r}. \end{align*} Since \begin{align*} \det(B)=pqr, \end{align*} we obtain \begin{align*} \det C_{T_{p,q,r}} &=pqr\left(2-\frac{p-1}{p}-\frac{q-1}{q}-\frac{r-1}{r}\right)\\ &=pqr\left(\frac1p+\frac1q+\frac1r-1\right). \end{align*} Positive definiteness implies that this determinant is positive. Because $pqr>0$, the required numerical restriction is \begin{align*} \frac1p+\frac1q+\frac1r>1. \end{align*} [/guided] [/step] [step:Solve the branch length inequality] Let $2 \le p \le q \le r$ be integers satisfying \begin{align*} \frac1p+\frac1q+\frac1r>1. \end{align*} If $p \ge 3$, then $q \ge 3$ and $r \ge 3$, so \begin{align*} \frac1p+\frac1q+\frac1r \le 1, \end{align*} a contradiction. Hence $p=2$. If $q \ge 4$, then $r \ge q \ge 4$, and therefore \begin{align*} \frac1p+\frac1q+\frac1r \le \frac12+\frac14+\frac14 =1, \end{align*} again a contradiction. Thus $q=2$ or $q=3$. If $q=2$, then $r \ge 2$ is arbitrary. The corresponding three-armed tree has two arms of length $2$ and one arm of length $r$; it has $r+2$ vertices and is the diagram $D_{r+2}$. Since $r \ge 2$, this gives $D_\ell$ for $\ell \ge 4$. If $q=3$, then \begin{align*} \frac12+\frac13+\frac1r>1 \end{align*} is equivalent to $r<6$. Since $r \ge 3$, this gives \begin{align*} r=3,\quad r=4,\quad r=5. \end{align*} The corresponding diagrams are respectively $E_6$, $E_7$, and $E_8$. Combining this with the path case, every connected simply laced positive definite diagram is one of \begin{align*} A_\ell \quad (\ell \ge 1), \qquad D_\ell \quad (\ell \ge 4), \qquad E_6,\ E_7,\ E_8. \end{align*} [/step] [step:Realize the classical diagrams by coordinate root systems] For $\ell \ge 1$, let $(e_1,\dots,e_{\ell+1})$ be the standard orthonormal basis of $\mathbb{R}^{\ell+1}$, and define \begin{align*} \Phi(A_\ell)=\{e_i-e_j : 1 \le i \ne j \le \ell+1\}. \end{align*} This is a finite reduced crystallographic root system in the hyperplane $\sum_{i=1}^{\ell+1} x_i=0$. The simple roots \begin{align*} \alpha_i=e_i-e_{i+1}, \qquad 1 \le i \le \ell, \end{align*} satisfy $(\alpha_i,\alpha_i)=2$, $(\alpha_i,\alpha_{i+1})=-1$, and $(\alpha_i,\alpha_j)=0$ when $|i-j|>1$. Hence their Dynkin diagram is $A_\ell$. For $\ell \ge 4$, let $(e_1,\dots,e_\ell)$ be the standard orthonormal basis of $\mathbb{R}^\ell$, and define \begin{align*} \Phi(D_\ell)=\{\pm e_i \pm e_j : 1 \le i<j \le \ell\}. \end{align*} This is a finite reduced crystallographic root system. Choose simple roots \begin{align*} \alpha_i &= e_i-e_{i+1}, \qquad 1 \le i \le \ell-1,\\ \alpha_\ell &= e_{\ell-1}+e_\ell. \end{align*} A direct inner-product computation gives $(\alpha_i,\alpha_i)=2$ for all $i$, edges along the chain $\alpha_1,\dots,\alpha_{\ell-1}$, and the additional edge between $\alpha_{\ell-2}$ and $\alpha_\ell$, with all other non-diagonal inner products equal to $0$. Hence the Dynkin diagram is $D_\ell$. [guided] The converse starts with the standard coordinate root systems. For type $A_\ell$, the roots are all differences $e_i-e_j$ inside the hyperplane of $\mathbb{R}^{\ell+1}$ where the coordinate sum is zero: \begin{align*} \Phi(A_\ell)=\{e_i-e_j : 1 \le i \ne j \le \ell+1\}. \end{align*} The usual simple roots are consecutive differences, \begin{align*} \alpha_i=e_i-e_{i+1}, \qquad 1 \le i \le \ell. \end{align*} Each has squared length $2$. Adjacent simple roots satisfy \begin{align*} (\alpha_i,\alpha_{i+1}) =(e_i-e_{i+1},e_{i+1}-e_{i+2}) =-1, \end{align*} and non-adjacent simple roots have inner product $0$. Since the simply laced Dynkin diagram has an edge exactly when the inner product is $-1$, this gives the path $A_\ell$. For type $D_\ell$, the roots are \begin{align*} \Phi(D_\ell)=\{\pm e_i \pm e_j : 1 \le i<j \le \ell\}. \end{align*} Take \begin{align*} \alpha_i &= e_i-e_{i+1}, \qquad 1 \le i \le \ell-1,\\ \alpha_\ell &= e_{\ell-1}+e_\ell. \end{align*} The roots $\alpha_1,\dots,\alpha_{\ell-1}$ form a chain. The last root $\alpha_\ell$ is orthogonal to $\alpha_i$ for $i<\ell-2$, and \begin{align*} (\alpha_{\ell-2},\alpha_\ell) =(e_{\ell-2}-e_{\ell-1},e_{\ell-1}+e_\ell) =-1. \end{align*} Also \begin{align*} (\alpha_{\ell-1},\alpha_\ell) =(e_{\ell-1}-e_\ell,e_{\ell-1}+e_\ell) =0. \end{align*} Thus the branch occurs at $\alpha_{\ell-2}$, giving exactly $D_\ell$. [/guided] [/step] [step:Realize the exceptional diagrams inside the standard $E_8$ root system] Let $(e_1,\dots,e_8)$ be the standard orthonormal basis of $\mathbb{R}^8$, and define \begin{align*} \Phi(E_8) &= \{\pm e_i \pm e_j : 1 \le i<j \le 8\}\\ &\qquad \cup \left\{ \frac12\sum_{i=1}^8 \varepsilon_i e_i : \varepsilon_i \in \{\pm 1\},\ \prod_{i=1}^8 \varepsilon_i=1 \right\}. \end{align*} This is the standard finite reduced crystallographic root system of type $E_8$. Define roots \begin{align*} \alpha_1&=\frac12(e_1-e_2-e_3-e_4-e_5-e_6-e_7+e_8),\\ \alpha_2&=e_1+e_2,\\ \alpha_3&=e_2-e_1,\\ \alpha_4&=e_3-e_2,\\ \alpha_5&=e_4-e_3,\\ \alpha_6&=e_5-e_4,\\ \alpha_7&=e_6-e_5,\\ \alpha_8&=e_7-e_6. \end{align*} Each $\alpha_i$ belongs to $\Phi(E_8)$ and has squared length $2$. Direct computation gives the nonzero off-diagonal inner products \begin{align*} (\alpha_1,\alpha_3)&=-1,\\ (\alpha_2,\alpha_4)&=-1,\\ (\alpha_3,\alpha_4)&=-1,\\ (\alpha_4,\alpha_5)&=-1,\\ (\alpha_5,\alpha_6)&=-1,\\ (\alpha_6,\alpha_7)&=-1,\\ (\alpha_7,\alpha_8)&=-1, \end{align*} and all other off-diagonal inner products are $0$. Therefore the Dynkin diagram of $\alpha_1,\dots,\alpha_8$ is $E_8$. The subsets $\{\alpha_1,\dots,\alpha_7\}$ and $\{\alpha_1,\dots,\alpha_6\}$ have the induced diagrams $E_7$ and $E_6$, respectively. The root subsystems generated by these subsets inside $\Phi(E_8)$ are finite, reduced, and crystallographic because they are closed subsystems of the finite reduced crystallographic root system $\Phi(E_8)$. Hence $E_6$, $E_7$, and $E_8$ are all realized by finite reduced crystallographic root systems. Together with the coordinate realizations of $A_\ell$ and $D_\ell$, this proves the converse and completes the classification. [/step]