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

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

• I see, if I just pick one color for even and another color for odd then the adjacent points in $\mathbb Z^2$ are distinguishable. Thanks @Brian M. Scott Apr 3, 2021 at 19:56
• @WhyGraph_: That’s right. You’re welcome. Apr 3, 2021 at 20:01
• 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.
• nice(+1) and detail answer. Thanks @Sandipan Dey Apr 4, 2021 at 14:50