Proof that the rational unit distance graph is Bipartile I was browsing StackExchange and found this problem posted The rational unit distance graph is bipartite
I found the question and the proof for part a.) very interesting, yet, i cannot seem to piece together the proof for part b and would really appreciate the help. Thank you!
The question is quoted below:

I am trying questions from a Graph theory book by Bondy and Murty. I
  stumbled across a neat looking problem.

The unit distance graph on a subset $V$ of $\mathbb{R}^2$ is the graph with vertex set $V$ in which two vertices $(x_1, y_1)$ and
    $(x_2, y_2)$ are adjacent if their euclidean distance is equal to $1$,
    that is, if $(x_1 − x_2)^2 + (y_1 − y_2)^2 = 1$. When $V = \mathbb{Q}^2$, this graph is called the rational unit distance graph,
    and when $V = \mathbb{R}^2$, the real unit distance graph.
a) Let $V$ be a finite subset of the vertex set of the infinite $2$-dimensional integer  lattice, and let $d$ be an odd positive
    integer. Denote by $G$ the graph with vertex set $V$ in which two
    vertices $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent if their euclidean
    distance is equal to $d$. Show that $G$ is bipartite.
b) Deduce that the rational unit distance graph is bipartite.
c) Show, on the other hand, that the real unit distance graph is not bipartite.

I am totally stumped by this question. All my attempts to search 'unit
  distance graph' mainly returns coloring questions :(

Thank you for your help!
 A: For part (a), the solution to the linked question shows that there can be no integer points $(x_1, y_1), \dots, (x_{2k+1}, y_{2k+1})$ forming an odd cycle, if adjacent points need to be a distance $d$ apart, where $d$ is an odd integer.
For part (b), then, we'd like to prove that there can be no rational points $(x_1, y_1), \dots, (x_{2k+1}, y_{2k+1})$ forming an odd cycle, if adjacent points need to be $1$ apart.
This gives us the equations $(x_i - x_{i+1})^2 + (y_i - y_{i+1})^2 = 1$ for $i=1, \dots, 2k$ and $(x_1 - x_{2k+1})^2 + (y_1 - y_{2k+1})^2 = 1$, but the $x_i, y_i$ are all rational numbers. Let $a_1, \dots, a_{2k+1}$ be the difference in the first square in each equation, and $b_1, \dots, b_{2k+1}$, so that we have $a_i^2 + b_i^2 = 1$ for $i=1,\dots,2k+1$.
Suppose we had a solution to this in rational numbers. Then we could multiply through by the square of the lowest common denominator $L$ of the $a_i$ and the $b_i$, to get equations $(La_i)^2 + (L b_i)^2 = L^2$ for $i=1, \dots, 2k+1$. Note that $La_i, Lb_i$ are all integers.
There are two cases. Either $L^2$ is an odd integer, in which case the argument in part (a) shows that this is impossible. Or, $L$ is even. 
In that case, there must be one of the $a$'s or $b$'s (without loss of generality, $a_i$) such that $La_i$ is odd: if multiplying by $L$ had made all of them even, then multiplying by $\frac L2$ would have already cleared denominators.
But now, in the equation $(La_i)^2 + (Lb_i)^2 = L^2$, if we take it modulo $4$, we have $(La_i)^2 \equiv 1 \pmod 4$ and $L^2 \equiv 0 \pmod 4$, so $(Lb_i)^2 \equiv 3 \pmod 4$, which cannot happen for any integer $Lb_i$. This is a contradiction, so the second case cannot occur.
