The Weisfeiler-Leman dimension 
of a finite graph 
,
sometimes known as the WL dimension, is the smallest positive
integer 
such that the 
-dimensional Weisfeiler-Leman
algorithm distinguishes 
from every graph not isomorphic
to 
(Grohe 2017).
The Weisfeiler-Leman dimension of a graph 
with vertex count 
satisfies
 |
(Kiefer 2020, p. 37). The only graph with 
is the singleton
graph 
.
For a nonempty graph 
, let 
range over its connected
components, and set 
. Any component
requiring 
dimensions gives the lower bound 
. Conversely, when 
, the 
-dimensional Weisfeiler-Leman
algorithm detects whether vertices lie in the
same connected component and retains the 
-dimensional
information within each component. It can
therefore identify 
once 
is at least both 2 and 
. Thus
 |
In particular, 
equals the maximum component dimension when that maximum
is at least 2 (Kiefer et al. 2019, Section 4).
The condition that the maximum component dimension is at least 2 is essential. The stronger claim (Schweitzer 2018) that the
equality holds whenever 
, even if every component
has dimension 1 is incorrect. Indeed, 
while 
. Color refinement
does not distinguish 
from 
. Any graph it does not distinguish
from 
has six vertices of vertex
degree 2 and is therefore either 
or 
, and the two-dimensional Weisfeiler-Leman
algorithm distinguishes these two graphs by the numbers
of common neighbors of nonadjacent vertices.
A finite graph 
has Weisfeiler-Leman dimension 1 iff color refinement, the one-dimensional Weisfeiler-Leman
algorithm, distinguishes 
from every graph not isomorphic
to 
(Arvind et al. 2017). Such a graph is amenable.
The characterization is structural rather than a short list of familiar graph families. In the formulation of Arvind et al. (2017,
Theorem 9), the stable color classes produced by color
refinement are regarded as cells. Each cell induces an empty
graph, a complete graph, a perfect
matching or its graph complement, or the
cycle graph 
. Between two cells, the induced bipartite
graph is an empty graph, a complete
bipartite graph, a graph disjoint union
of isomorphic star
graphs whose centers all lie in one cell, or the bipartite
complement of such a graph disjoint union.
Form a graph whose vertices
are the cells and whose edges join pairs
for which the induced bipartite graph is neither
an empty graph nor a complete
bipartite graph. Every component of this
graph is a rooted tree with
a smallest cell as its root vertex. Cell sizes do
not decrease away from the root vertex, and each tree has at most one cell whose induced graph
is neither an empty graph nor a complete
graph. If present, that cell has minimum size. Kiefer
et al. (2015) independently obtained an equivalent characterization.
Unfortunately, a complete description of the graphs of WL-dimension 2 seems intractable (Li et al. 2026).
The only regular graphs with Weisfeiler-Leman dimension 1 are the cocktail party graphs, complete
graphs, empty graphs, ladder
rung graphs, and the cycle graph 
(Arvind et al. 2017, Schweitzer 2018, Fuhlbrück
et al. 2020).
The Weisfeiler-Leman dimension of a tree or forest is 1 (Arvind et al. 2015), of a distance-hereditary
graph is at most 2 (Gavrilyuk et al. 2020), and of a planar
graph is at most 3 (Kiefer et al. 2019, Li et al. 2026). The stable coloring produced by the two-dimensional Weisfeiler-Leman algorithm on a graph 
determines a coherent configuration. This
configuration is called Schurian
when its color classes are exactly the orbitals of 
on ordered pairs of vertices.
The homogeneous coherent configuration
case is a Schurian scheme. Li et al. (2026)
proved that a Schurian graph has Weisfeiler-Leman
dimension at most 2 when it is polyhedral and
conjectured that every polyhedral graph is a
Schurian graph.
