Combinatorics graphs for $2k+1$ representatives from $k $ different countries.

Question

I'm having trouble with the following question :

Representatives from $1+2k$ countries come to an international conference, $k$ representatives from each country. Is it possible to seat the $k(2k+1)$ representatives around a round table so that each pair of countries has Representatives sitting side by side?"

At first I thought of making a graph with $2k+1$ vertices, every edge will represent two representatives from $2$ different countries. Then prove that an Eulerian cycle exists.

I'm not sure if that's the right way to approach this question, I would appreciate advices for this problem.

Answer 1

Consider a complete graph of size $1+2k$. Each vertex represents a country, and so, it has $2k$ edges with each edge representing two representatives sitting next to each other. In total, this graph has $(1+2k)((1+2k) - 1)/2 = k(1+2k)$ edges.

From Wikipedia: An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component.

So, yes, this graph has a Eulerian circuit (complete graphs have Eulerian circuits if and only if the number of vertices is odd).

It remains to show that there is a seating arrangement that corresponds to this graph: Pick any Eulerian cycle. Every time we visit a vertex $v_i$ ($i \in \{1,...,2k+1\})$, we add a new representative from country $i$ in clockwise order, and that should do it.

Answer 2

Hint.

1. Take a complete graph on $2k+1$ vertices.
2. Prove that it has an Eulerian cycle.
3. Construct by Eulerian's cycle the required representation arrangement.

The cases $k=1,2,3$ are very useful.