1.6.4. UNIT DISTANCE GRAPH. The unit distance graph on a subset V of R" is the graph with vertex set V in which two vertices (71, y1) and (22, 32) are adjacent if their Euclidean distance is equal to 1, that is, if (11 -12)2 4 (3/1 - 1/2)?= 1. When V = Q2, this graph is called the rational unit distance graphs, and when V = R?, the real unit distance graph. (a) Let V be a finite subset of the vertex set of the infinite 2-dimensional integer lattice (see Figure 1.27), and let d be an odd positive integer. Denote by G the graph with vertex set V in which two vertices (21, y1) and (12, 12) are adjacent if their Euclidean distance is equal to d. Prove that G is bipartite. Figure 1.27 Note. In Theorem 4.7 it is shown that a graph is bipartite if and only if it contains no odd cycle. You may assume this result