Associativity of graphs

Question

I have a binary operation $\star$ on a set of graphs such that the $\star$ is an associative (so far i have tried) that is for any three graphs $A$, $B$ and $C$ $\implies (A\star B)\star C=A\star(B\star C)$. But when i take four graphs, $A, B, C$ and $D$, then the following inequality holds: $[(A\star B)\star C]\star D\neq A\star[B\star(C\star D)]$. Now, what can be said about such operations? Can i still call the $\star$ associative?

Answer 1

This is not possible: if a binary operation $\star$ is associative, then it also satisfies $$((A\star B)\star C)\star D= A\star(B\star(C\star D)).$$ Indeed, we have $$((A\star B)\star C)\star D=(A\star B)\star (C\star D)=(A\star (B\star (C\star D))$$ where each step is an application of associativity. So in fact you can use your example where $$((A\star B)\star C)\star D\neq A\star(B\star(C\star D))$$ to find a counterexample to associativity (namely, one of the two steps of the proof above must fail).

More generally, by a similar argument and induction on $n$, you can prove that any two ways to parenthesize an $n$-fold product must be equal (see Let $a_1,a_2,a_3,...,a_n$ be elements of a group $(G,*)$. Show by induction that $a_1*a_2*a_3...*a_n$ always gives the same answer. for instance).