This property is useful for problems like the seating arrangement, where each person must have different neighbors every day. Each edge-disjoint Hamiltonian circuit corresponds to a unique arrangement.

Approach

In a complete graph with N vertices (where N is odd and N > 1), the number of edge-disjoint Hamiltonian circuits is (N-1)/2.
Each circuit represents a unique seating arrangement where no two people have the same neighbors as before.
This is because each Hamiltonian circuit uses N edges, and the total number of edges in a complete graph is N(N-1)/2.
The construction can be visualized by incrementally increasing the "distance" between neighbors in the seating arrangement each day.
For even N, such a set of edge-disjoint Hamiltonian circuits does not exist for all edges.

Example Visualization

Suppose N = 7. The following image shows how edge-disjoint Hamiltonian circuits can be constructed by increasing the "distance" between neighbors each day:

seating-arrangement-problem-viz1.excalidraw

Day 1: Each person sits next to their immediate neighbors. Day 2: Each person sits with neighbors one seat apart from the previous day. Day 3: Each person sits with neighbors two seats apart from the previous day. After (N-1)/2 days, all possible edge-disjoint arrangements are exhausted.

Code

[{"language":"C++","code":"class Solution {\npublic:\n  int maxSeatingArrangements(int n) {\n    if (n <= 1 || n % 2 == 0) return 0;\n    return (n - 1) / 2;\n  }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">  int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maxSeatingArrangements</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    if</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> ||</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">%</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 2</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> ==</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">return</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    return</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">-</span><span style

Related Tags