1.6.4. UNIT DISTANCE GRAPH. The unit distance graph on a subset V of R is the...

Transcribed Image Text:

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 (T1, y₁) and (2, 2) are adjacent if their Euclidean distance is equal to 1, that is, if (T1 - T2)² + (y1 - 32)² = 1. When V = Q², this graph is called the rational unit distance graphs, and when V = R2, 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 (T1, y₁) and (T2, 92) 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. 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 (T1, y₁) and (2, 2) are adjacent if their Euclidean distance is equal to 1, that is, if (T1 - T2)² + (y1 - 32)² = 1. When V = Q², this graph is called the rational unit distance graphs, and when V = R2, 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 (T1, y₁) and (T2, 92) 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.

Answer rating: 100% (QA)

Step 11 Final answer First of all the definition of bipartite graph is that a graph G is said to be ... View the full answer