Dimension (graph theory)
In mathematics, and particularly in graph theory, the dimension of a graph is the least integer such that there exists a "classical representation" of the graph in the Euclidean space of dimension with all the edges having unit length. In a classical representation, the vertices must be distinct points, but the edges may cross one another. The dimension of a graph is written: formula_1. For example, the Petersen graph can be drawn with unit edges in formula_2, but not in formula_3: its dimension is therefore 2 (see the figure to the right). This concept was introduced in  1965 by Paul Erdős, Frank Harary and William Tutte. It generalises the concept of unit distance graph to more than 2 dimensions. Examples. Complete graph. In the worst case, every pair of vertices is connected, giving a complete graph. To immerse the complete graph formula_4 with all the edges having unit length, we need the Euclidean space of dimension formula_5. For example, it takes two dimensions to immerse formula_6 (an equilateral triangle), and three to immerse formula_7 (a regular tetrahedron) as shown to the right. In other words, the dimension of the complete graph is the same as that of  the simplex having the same number of vertices. Complete bipartite graphs. All star graphs formula_9, for formula_10, have dimension 2, as shown in the figure to the left. Star graphs with equal to 1 or 2 need only dimension 1. The dimension of a complete bipartite graph formula_11, for formula_10, can be drawn as in the figure to the right, by placing vertices on a circle whose radius is less than a unit, and the other two vertices one each side of the plane of the circle, at a suitable distance from it. formula_13 has dimension 2, as it can  be drawn as a unit rhombus in the plane. To summarise: Dimension and chromatic number. This proof also uses circles. We write for the chromatic number of , and assign the integers formula_15 to the colours. In formula_16-dimensional Euclidean space, with its dimensions denoted formula_17, we arrange all the vertices of colour arbitrarily on the circle given by formula_18. Then the distance from a vertex of colour to a vertex of colour is given by formula_19. Euclidean dimension. The definition of the dimension of a graph given above says, of the minimal- representation: This definition is rejected by some authors . A different definition was proposed in 1991 by Alexander Soifer, for what he termed the Euclidean dimension of a graph. Previously, in 1980, Paul Erdős and Miklós Simonovits had already proposed it with the name faithful dimension. By this definition, the minimal- representation is one such that two vertices of the graph are connected "if and only if" their representations are at distance 1. The figures opposite show the difference between these definitions, in the case of a wheel graph having a central vertex and six peripheral vertices, with one spoke removed. Its representation in the plane allows two vertices  at distance 1, but they are not connected. We write this dimension as formula_20. It is never less than the dimension defined as above: Euclidean dimension and maximal degree. Paul Erdős and Miklós Simonovits proved the following result in 1980: Computational complexity. It is NP-hard, and more specifically complete for the existential theory of the reals, to test whether the dimension or the Euclidean dimension of a given graph is at most a given value. The problem remains hard even for testing whether the dimension or Euclidean dimension is two.