So i started studying this book on graph theory by Nar Singh Deo, and fairly early on the following problem gets introduced:
n people decide to meet for lunch every day, however they decide that they will sit in a manner such that no two same people sit together any of the days.
How many days can this go on?
If we hypothesize a complete graph of order n, and find a set of disjoint Hamiltonian cycles, the cardinality of this set is our answer. (Here, by disjoint Hamiltonian cycles i mean cycles where the edges do not overlap).
If we imagine a circle, with points numbered 1, 2, 3, ... n , and we skip 1, then 2, then 3, etc we will start to find potential answers / potential Hamiltonian paths. However, the path will only be Hamiltonian if we skip by a number k such that gcd(k, n) = 1. Which means, that the number of potential paths is $\phi(n)$ (which is the Euler Totient function)
I took 9 as an example case, and tried to work it out :
1 2 3 4 5 6 7 8 9
1 3 5 7 9 2 4 6 8
1 5 9 4 8 3 7 2 6
1 6 2 7 3 8 4 9 5
1 8 6 4 2 9 7 5 3
1 9 8 7 6 5 4 3 2
So it can be seen that, after the half way point, the paths begin to mirror themselves. The first three cycles satisfy the condition. So the answer = 3 or $\frac{\phi(9)}{2}$. I hypothesized for the answer to be $$\frac{\phi(n)}{2}$$ for an arbitrary n, However, the book gives an answer $$\frac{n-1}{2}$$ if n is odd and $$\frac{n-2}{2}$$ if n is even, which just seems wrong. What am i missing? And what exactly is the relationship between the Euler Totient function and Hamiltonian paths?
Case $n$ is even: see Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.
Case $n$ is odd: see Hamiltonian Cycle Problem