Show that the graph $G$ is $2$ colorable

Question

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.

Answer 1

HINT: Consider whether $m+n$ is even or odd.

Answer 2

• 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.