2n ambassador problem

Question

I found this problem, from the book Problem-Solving Strategies by Engel. And I found they have solved it in a very elegant(read: complex) way for me to comprehend. On the contrary, I came up with a different (read: easier) proof. But there might be loopholes in it. I am a newbie in discrete maths and I would be glad if someone could possibly point out a mistake in my proof.

2n ambassadors are invited to a banquet. Every ambassador has at most n−1 enemies. Prove that the ambassadors can be seated around a round table, so that nobody sits next to an enemy.

Proof: Say we place all people around a round table in any arbitrary order. Say H is the total sum of all cases when we have a person sitting adjacent to his enemy. If H=0, we are done. Otherwise,

Case 1: P is sitting adjacent to 2 enemies. Leaving P and his 2 enemies, we have at most n-3 enemies and at least n-1 friends. Placing the n-3 enemies, we have n-2 gaps between them, by pigeonhole principle, we see at least n-1 people in n-2 gaps, hence at least 1 gap should contain 2 friends thus we place P between them and H decreases.

Case 2: P is sitting adjacent to 1 enemy. Leaving P and his enemy and the friend beside him, we have at most n-2 enemies and at least n-2 friends. Placing the n-2 enemies, we have n-1 gaps between them, so at least one gap remains empty, we place P between 2 enemies then do according to case 1 and H decreases.

So H $>=$ 0 always so we cannot keep on decreasing H forever, we have to reach a minimum, hence H=0 will be the minimum and then we will be done.

btw how do you write bullet points in here? \begin{enumerate} fails here — Alex, Aug 20 '21 at 05:17
FYI, to write bullet points, just use "- " (without the double quotes) at the start of a line. For more general info on this, called markdown, see Markdown help. — John Omielan, Aug 20 '21 at 05:27

score 4 · Accepted Answer · answered Aug 20 '21 at 05:28

In case $2$, $H$ might not decrease – after $P$ is moved between two non-enemies $P$'s former neighbours might themselves be enemies, cancelling the decrease in $H$. The proof is invalid.

The original problem is in fact a restating of Dirac's theorem: if every vertex has at least $n/2$ neighbours the graph is Hamiltonian. The ambassadors are vertices and every two non-enemies are connected by an edge; since each vertex has at most $n-1$ non-neighbours, each has at least $n$ neighbours.

2n ambassador problem

1 Answers1

Linked