Note on induced subgraphs of the unit distance graph \(E^ n\) (Q1106853): Difference between revisions

The unit distance graph \(E^ n\) is the graph whose vertices are the points in Euclidean n-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for any n there is a finite bipartite graph which cannot be embedded in \(E^ n\) as an induced subgraph and that every finite graph with maximum degree d can be embedded in \(E^ N\), \(N=(d^ 3-d)/2\), as an induced subgraph.