Are these graphs all bipartite? Given a number $D >0$, define a graph $G_D$ as follows.
The vertices of $G_D$ correspond to points in the two-dimensional integer lattice $\mathbb{Z} \times \mathbb{Z}$.
A pair of vertices $\{ p,q \}$ is defined to be adjacent if $d(p,q)=D$.
My question: is the graph $G_D$ bipartite for every choice of $D$?
 A: Key step: Prove by contradiction that no odd cycle exists, thus we can conclude immediately that the graph can be made bipartite.
Consider the possible value of $D^2$. Since that is the square of distance between 2 integer points, it is of the form $a^2 + b^2$. Then, we get that $ D^2 \equiv 0, 1, 2 \pmod{4} $.
If $ D \equiv 1 \pmod{4} $, then consider the parity of the points $(x,y) \rightarrow x+y$. Any 2 vertices that are connected by an edge must have opposite parity, hence no odd cycle exists.
If $ D \equiv 2 \pmod{4} $, if $(x_1, y_1 )$ is connected to $(x_2, y_2)$, then it follows that $x_1 - x_2 \equiv y_1 - y_2 \equiv 1 \pmod{2}$. What this means is that the parity of $x$ itself alternates, hence no odd cycle exists.
If $ D \equiv 0 \pmod{4} $, if $(x_1, y_1 )$ is connected to $(x_2, y_2)$, then it follows that $x_1 - x_2 \equiv y_1 - y_2 \equiv 0 \pmod{2}$. Now, consider any odd cycle, WLOG one of the points is $(0,0)$. Then, all of the coordinates of this cycle must be even. Dividing throughout by 2, we get a cycle of points whose distance is $ D^* = \frac{D}{4} $. Continue dividing until we we do not have $ D^* \equiv 0 \pmod{4}$, and thus were are in one of the above cases, hence no odd cycle exists.
A: First, prove that $G_D$ contains no cycle of odd length. The proof that a graph is bipartrite if and only if it contains no odd cycle is a famous graph theory concept. I will leave this as an exercise but there should be plenty of proofs on the internet if you are stuck.
Suppose that $G_D$ contains an odd cycle consisting of vertices $v_1, v_2, \cdots, v_n$ where $n$ is odd. Consider the vectors $v_i = a_i \hat{i}+b_i \hat{j}$ that takes vertex $v_i$ to $v_{i+1}$ where the indices are read modulo $n$. Since our $n$ vertices form a cycle, we know $$\sum_i v_i = 0$$ and breaking into components gives $$\sum_i a_i = 0, \sum_i b_i = 0.$$
Then for all $i$, we know $a_i^2+b_i^2 = D^2$ which is an integer since our vectors take integers to integers. Now
$$0 = \left(\sum_i a_i \right)^2+\left(\sum_i a_i \right)^2$$ or 
$$ 0 = nD^2+2k $$ for some integer $k$. Therefore, it follows that $2|D^2$ since $n$ is odd. Hence $a_i, b_i$ have the same parity. If they are both even, we can consider $G_{D/4}$ and repeat the same argument as above. So they are both odd which means $2|D^2$ but $4 \nmid D^2$. Now we know that
$$k = \sum a_ia_j+\sum b_ib_j, i \ne j.$$
Since $k$ is the sum of $2 \dbinom{n}2$ terms, all odd, we have $k$ is also even and from $0 = nD^2+2k$, we get $4|D^2$, contradiction. 
(Interestingly, we can use an identical proof to say that no regular polygon with $\ge 5$ sides can have integer coordinates. )
