# Graph cartesian products

On the basis that knowing some more about Graph Theory won’t do me any harm when thinking about operating system behaviour, I am reading about that too right now.

But I found the book’s explanation of a Graph Cartesian Product rather less than full, so here is my attempt to make it a bit clearer.

Say we have graph $G_1$ with vertices $(v_1, v_2, v_3)$ and graph $G_2$ with vertices $(w_1, w_2, w_3, w_4)$, then our cartesian product graph is $G_3$ with vertices $((v_1, w_1), (v_1, w_2), (v1, w_3), (v_2, w_4),(v_2, w_1), (v_2, w_2), (v2, w_3), (v_2, w_4),(v_3, w_1), (v_3, w_2), (v3, w_3), (v_3, w_4))$

Which vertices in this new graph are adjacent?

The vertices are adjacent if – and only if – taking the new vertices to be of the form $(v_n, w_n) (v^{\prime}_n, w^{\prime}_n)$ – if $v_n = v^{\prime}_n$ and $w_n$ is adjacent to $w^{\prime}_n$ in $G_2$ OR $w_n = w^{\prime}_n$ and $v_n$ is adjacent to $v^{\prime}_n$ in $G_1$.