# associativity in graph theory

Can anybody help me in clearing the facts how the associativity was proved in cartesian product of 3 graphs, and thus showing isomorphism. I can easily solve for the case when its two graphs. Taking three graphs is not clear to me. Kindly help. Thanks a lot to all.

-

I will try to present some intuition, once you have it, it should be fairly straightforward (to prove it formally, it's enough to expand the definitions and it's done, so I guess that's not a problem here). Illustrations are at the bottom, sorry for the rainbow colors, but without them it would be even harder to digest.

It's sometimes beneficial to think about the Cartesian product of graphs in analogy to the ordinary Cartesian product. For example, product of two lines gives us a plane, product of two discrete lines results in a discrete plane. Similarly, if we arrange the vertices of the graph into a finite and discrete line, then what we will get would look like finite discrete plane (with appropriate edges). Also, as in $\mathbb{N^2}$, you can go north and south, and east and west, but you cannot use diagonals, in similar fashion you can use $\color{blue}{\text{blue}}$ edges to go east and west and you can use $\color{green}{\text{green}}$ edges to go north and south, but there are no diagonal edges.

When you add a third graph, things doesn't change much. As you can produce $\mathbb{N^3}$ as $\mathbb{N}^2 \times \mathbb{N}$ or $\mathbb{N} \times \mathbb{N}^2$, the final structure doesn't change. This is because each graph allows you to move in some "dimension", but nothing more, there are no diagonals (which might make the product non-associative). If you want to go up or down, you have to use $\color{red}{\text{red}}$ edges no matter whether the "base graph" is, $\color{blue}{\text{blue}} \times \color{green}{\text{green}}$ or just $\color{green}{\text{green}}$. Whatever order you would take the product of graphs, the only edges are $\color{blue}{\text{blue}}$ to move between $(\color{blue}{x_1},y,z)$ and $(\color{blue}{x_2},y,z)$, $\color{green}{\text{green}}$ edges to move between $(x, \color{green}{y_1},z)$ and $(x,\color{green}{y_2},z)$ and finally $\color{red}{\text{red}}$ edges to move between vertices $(x, y, \color{red}{z_1})$ and $(x,y, \color{red}{z_2})$. Moreover, whatever order you would take the product of graphs, you will get all those edges, and as such, the graphs will be isomorphic.

I hope this helps $\ddot\smile$

-
(+1) Cool pictures! – Tunococ Aug 2 '13 at 10:16