Dimension (graph theory)

In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a 'classical representation' of the graph in the Euclidean space of dimension n with all the edges having unit length.Theorem — The dimension of a general complete bipartite graph K m , n {displaystyle K_{m,n}} , for m ≥ 3 {displaystyle mgeq 3} and n ≥ 3 {displaystyle ngeq 3} , is 4.To show that 4-space is sufficient, as with the previous case, we use circles.Theorem — The dimension of any graph G is always less than or equal to twice its chromatic number:This proof also uses circles.Theorem — The Euclidean dimension of a graph G is no more than twice its maximal degree plus one: In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a 'classical representation' of the graph in the Euclidean space of dimension n 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 G is written: dim ⁡ G {displaystyle dim G} . For example, the Petersen graph can be drawn with unit edges in E 2 {displaystyle E^{2}} , but not in E 1 {displaystyle E^{1}} : 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. In the worst case, every pair of vertices is connected, giving a complete graph. To immerse the complete graph K n {displaystyle K_{n}} with all the edges having unit length, we need the Euclidean space of dimension n − 1 {displaystyle n-1} . For example, it takes two dimensions to immerse K 3 {displaystyle K_{3}} (an equilateral triangle), and three to immerse K 4 {displaystyle K_{4}} (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. All star graphs K m , 1 {displaystyle K_{m,1}} , for m ≥ 3 {displaystyle mgeq 3} , have dimension 2, as shown in the figure to the left. Star graphs with m equal to 1 or 2 need only dimension 1.