ADE Classification - Labeled Graphs

Labeled Graphs

The ADE graphs and the extended (affine) ADE graphs can also be characterized in terms of labellings with certain properties, which can be stated in terms of the discrete Laplace operators or Cartan matrices. Proofs in terms of Cartan matrices may be found in (Kac 1990, pp. 47–54).

The affine ADE graphs are the only graphs that admit a positive labeling (labeling of the nodes by positive real numbers) with the following property:

Twice any label is the sum of the labels on adjacent vertices.

That is, they are the only positive functions with eigenvalue 1 for the discrete Laplacian (sum of adjacent vertices minus value of vertex) – the positive solutions to the homogeneous equation:

Equivalently, the positive functions in the kernel of The resulting numbering is unique up to scale, and if normalized such that the smallest number is 1, consists of small integers – 1 through 6, depending on the graph.

The ordinary ADE graphs are the only graphs that admit a positive labeling with the following property:

Twice any label minus two is the sum of the labels on adjacent vertices.

In terms of the Laplacian, the positive solutions to the inhomogeneous equation:

The resulting numbering is unique (scale is specified by the "2") and consists of integers; for E₈ they range from 58 to 270, and have been observed as early as (Bourbaki 1968).