Show that the graph $G$ is $2$ colorable 
Show that the graph $G$ is $2$ colorable which is define with vertex set $\mathbb Z^2$ where $(m,n)$ is adjacent to $(j,k)$ if $(m,n)\pm(1,0)=(j,k)$ or $(m,n)\pm(0,1)=(j,k)$.

I just draw a portion of the graph and it seems easily two colorable, like if I color a vertex with red and a different color (like blue) with all of it's adjacent vertices. But couldn't write it in a formal way.

I was doubt to write it in plain english because there are infintely many vertices to color, it would be nice if anyone show me the right way.
 A: HINT: Consider whether $m+n$ is even or odd.
A: *

*Using the theorem "A graph $G$ is bipartite if and only if it does not contain an odd cycle", since the grid graph does not contain an odd length cycle (prove with induction on the length of a cycle) it's a bipartite graph. For example, the following figure shows the original graph and an isomorphic bipartite representation:



*

*Another theorem: "Any bipartite graph $G$ is 2-colorable" (consider $V(G) = V_1 \cup V_2$, with $E(G)=\{(u,v):u \in V_1, v \in V_2\}$. Color vertices in $V_1$ with one color and those in $V_2$ with a different color).


*Combining the above two, the grid graph is 2-colorable.


*For example, consider the off-diagonals in the grid-graph and color with alternate colors as shown in the next figure.


*

*In this bipartite graph the unions of the alternate diagonals create the vertex sets $V_1$ and $V_2$.

Another way

*

*Prove that the vertices on the same diagonal and also on every alternate off diagonals will be at least $\pm(1,1)$ distance away from one another, hence can't be adjacent and can be colored with the same color.

