# Is there a Hamiltonian path? (i.e. can the general associative law be solved with Graph Theory?) [duplicate]

Consider the different bracketings of the summation $$1+2+3+4+5\,.$$ I've listed them all below: $$1+(2+(3+(4+5)))\,,\quad (1+((2+3)+4))+5\\ 1+(2+((3+4)+5))\,,\quad (1+(2+(3+4)))+5\\ 1+((2+(3+4))+5)\,,\quad ((1+2)+(3+4))+5\\ 1+(((2+3)+4)+5)\,,\quad (1+2)+((3+4)+5)\\ 1+((2+3)+(4+5))\,,\quad (1+2)+(3+(4+5))\\ (1+(2+3))+(4+5)\,,\quad ((1+2)+3)+(4+5)\\ ((1+(2+3))+4)+5\,,\quad (((1+2)+3)+4)+5$$ As we go down the first column, go up to the top of the second, and down the second column, we see that each of these bracketings are connected by a single use of the associative law. These different bracketings also exhaust the possibilities for $$1+2+3+4+5$$.

A similar pattern can be found for $$1+2+3$$ trivially and for $$1+2+3+4$$ almost trivially. These inspire the following graph-theoretic question:

Consider the graph whose nodes consist of the various "valid bracketings" of the summation underneath $$1+2+\cdots+n.$$ (In general, the number of nodes for this graph will be the $$n-1$$st Catalan number).

Two nodes will be connected by an edge if we may travel between the two via one application of the associative law.

Is there a Hamiltonian path in this graph?

The graph for $$1+2+3+4+5$$ is a 14-node graph where every node has a degree of three.

## marked as duplicate by Robert Wolfe, Eric Wofsey, Community♦Oct 19 '18 at 19:56

• This graph is known as the 1-skeleton of the $n$th associahedron. – Eric Wofsey Oct 19 '18 at 19:31
• I might mention for other readers that "valid bracketings" of a sum can be associated uniquely to a binary tree with $n$ leaves. And the associative law corresponds with a right/left rotation in a binary tree. The answer in the other question provides a paper (a lengthy though) which shows that there exists a hamiltonian path through the graph of binary trees with edges if the trees can be rotated to one-another. That does answer my question. – Robert Wolfe Oct 19 '18 at 19:55