Graph Dimension -- from Wolfram MathWorld

The dimension , also called the Euclidean dimension (e.g., Buckley and Harary 1988) of a graph, is the smallest dimension of Euclidean -space in which can be embedded with every edge length equal to 1 and every vertex position distinct (but where edges may cross or overlap and points may lie on edges that are not incident on them; Erdős et al. 1965).

Any connected graph with maximum vertex degree has graph dimension at most , with the exception of the utility graph (Frankl et al. 2018). Furthermore, any graph with chromatic number has graph dimension at most . This can be seen by partitioning the space into orthogonal two-dimensional planes, then in each plane placing the vertices with one color on a circle with radius centred on the plane's origin (so all points have a squared norm of 1/2) (J. Tan, pers. comm., Oct. 26, 2021).

For any nonempty graph , the graph Cartesian product satisfies

$e(G square K_2)={e(g) if e(G)>=2; e(G)+1 if e(G)=0 or 1$

(1)

(Erdős et al. 1965, Buckley and Harary 1988). While the theorem is stated as holding for "any" graph by both references, if is taken as the empty graph , then is isomorphic to the ladder rung graph . Yet for (since vertices may not overlap by the definition of graph dimension) and since each of the paths can be placed on a 1-dimensional line.

The singleton graph has graph dimension , the path graphs for have graph dimension , and in general, any graph with dimension 2 or less is said to be a unit-distance graph.

The dimension of the complete graph is (Erdős et al. 1965, Buckley and Harary 1988). For the complete bipartite graph with ,

$e(K_(m,n))={1 for m=n=1; 2 for m=n=2 or m=1, n>1; 3 for m=2, n>2; 4 m,n>=3$

(2)

(Erdős et al. 1965, Buckley and Harary 1988).

The dimension of is given by for (Erdős et al. 1965).

The hypercube graph has dimension for (Erdős et al. 1965).

The wheel graph has graph dimension 2 for (and hence is unit-distance) and dimension 3 otherwise (and hence is not unit-distance) (Erdős et al. 1965, Buckley and Harary 1988).

The following table summarizes the graph dimensions for various families of parametrized graphs.

graph	dimension
complete bipartite graph
complete graph
cycle graph	2
empty graph
generalized Petersen graph	2
grid graph
hypercube graph
path graph
star graph
wheel graph

The Hadwiger-Nelson problem asks for the chromatic number of the plane, i.e., the minimum number of colors needed to color the plane if no two points at unit distance one from one another are given the same color. It is therefore equivalent to asking for the largest possible chromatic number of a unit-distance graph in the plane (i.e., with dimension 2). The smallest unit-distance graph with chromatic number 4 is the Moser spindle on 7 vertices. As of late 2025, the value is known to be 5, 6, or 7, though no graphs with chromatic number larger than are known.

The following table summarizes the smallest known graphs with and .

			graph
2	5	509	509-Parts graph
2	5	510	510-Heule graph
2	5	510	510-Parts graph
2	5	517	517-Heule graph
2	5	525	525-Parts graph
2	5	529	529-Heule graph
2	5	529	529-Parts graph
2	5	553	553-Heule graph
2	5	553	553-Parts graph
2	5	610	610-Heule graph
2	5	633	633-Heule graph
2	5	803	803-Heule graph
2	5	826	826-Heule graph
2	5	874	874-Heule graph
2	5	1577	1577-Mixon graph
2	5	1581	de Grey graph
2	5	1585	1585-Mixon graph