Show that the maximum no. of bonds possible in a chain of $n$ elements, such that an element only bonds with another element once, is $n^2$

Question

Show that the maximum no. of bonds possible in a chain of $n$ elements, such that an element only bonds with another element once, is $n^2$. What this means will be clear by a representation;

As you can see if $n=1$, the max no. of chains will be $1^2$, if it's $2$ then the max no. becomes $2^2$ and so on. I want to show that the maximum no. of chains possible will be $n^2$.

Also for example, $☆—◌$ & $◌—☆$ are treated differently because it is >Star-bonds-with-circle and the latter is >Circle-bonds-with-star.

And also before anyone says there are $n$ elements and a element can bond with $n$ elements (including itself), and so it should be $n^2$. I want to see that this is possible, in a semi-rigorous way. What if it isn't possible, how do we prove that?

Another subset question that I came up with this, is to find how many different combinations are possible with $n$ elements so as to give $n^2$ chains. Maybe this one's for later, but still intriguing. I don't know a whole lot of terminology, symbols nor representations used in Graph theory, feel free to edit it in.

Answer 1

One way to describe such chains is to rephrase the problem as follows. We have a directed graph on $n$ vertices (such as $\{☆,□,◌\}$) in which each of the $n^2$ possible directed edges appears once. Here's an example of the graph for $n=3$:

A chain of length $n^2$ is a walk in this graph which visits each of the $n^2$ edges (the arrows) once. This is known as an Eulerian walk. For directed graphs, we know that whenever the number of edges going into a vertex equals the number of edges going out, an Eulerian walk (a) exists, and (b) always returns to the starting vertex at the end. (You may have noticed that in each of your chains, the first and last symbols are the same.)

So we know that there is a solution. What next?

By the BEST theorem, the number of such Eulerian circuits is equal to $$t(G)\prod_{v \in V} (\deg(v)-1)!$$ where $\deg(v)$ is the number of edges going out of a vertex $v$, and $t(G)$ is the number of arborescences of $G$ rooted at some vertex. Arborescences in general are complicated, but in the case of this graph, they are the same as trees on $n$ vertices, and there are $n^{n-2}$ of these by Cayley's theorem. Putting these together, we get that the number of Eulerian circuits is $$ n^{n-2} (n-1)!^n $$ although we should probably also multiply by $n^2$ to account for the fact that we can start an Eulerian circuit in any of $n^2$ places and get a chain. Simplifying, this gives us a final answer of $n!^n$ possible chains.

Answer 2

It is always possible to construct such a chain of length $n^2$ for any $n$.

I'll describe one way to construct it for $n=5$, but this is easily generalisable.

I'll label the nodes $a$ to $e$. The pattern starts like this:
$aaeadacab$
This used all combinations involving $a$ except for $ba$. Then do the same for $b$:
$bbebdbc$
This used all remaining combinations involving $b$ except for $cb$. Then do the same for $c$:
$ccecd$
This used all remaining combinations involving $c$ except for $dc$. Then do the same for $d$:
$dde$
And lastly return back to $a$ using those final unused combinations:
$eedcba$

Putting it together you get:
$aaeadacabbebdbccecddeedcba$

There are many other ways to put such a chain together.

Answer 3

You can always construct a $n^2$ long chain that has the properties you asked for in the following way: Pick an element $a_1$. The chain starts with $a_1-a_2-a_1-a_3-a_1-\dots-a_n$, now instead of going on $a_1$, which would make you unable to extend the chain, you go to another vertex and you repeat the procedure with $a_n$ as starting element, without going back to $a_1$. After having done so several times you will only have to go through those missing links.