edited by
214 views
0 votes
0 votes

You are organizing a party involving $2n$ diplomats. Each pair of diplomats are either friends or enemies. You have managed to invite an excellent set of guests, each of whom has more friends than enemies (among the other guests). Can you now seat them at a round table so that everyone has two friends as their neighbours. (Hint: Model this situation as an appropriate graph so that the desired seating arrangement is a Hamiltonian path.)

edited by

1 Answer

0 votes
0 votes
Let $G(V,E)$ be the simple undirected graph where $V = \{v_1, v_2, \dots, v_{2n}\}$ and $E = \{(v_i,v_j) | v_i \text{ and } v_j \text{ are friends}\}$. Now, it is given that every $v_i$ has more friends than enemies. This implies that any $v_i$ has atleast $n$ friends and atmost $n-1$ enemies.

Mathematically, $\forall_i \ deg(v_i) \ge n$, in other words, every vertex of graph $G$ has degree more than $n$.

If total guests are $2$, then both must be friends and we will have a hamiltonian path.

If total guests are $2n\ge4$ and degree of every vertex is atleast $n$, then graph is Hamiltonian. ($\textbf{Dirac's Theoram}$)

Presence of hamiltonian cycle shows that there exist a sequence of $2n$ vertices where every two consecutive vertices are connected implying that both are friends.

Hence, we can seat them around the round table while making sure that everyone has two friends as their neighbours.

Related questions

363
views
0 answers
1 votes
admin asked Jul 22, 2022
363 views
A Muller automaton is defined as a tuple $\text{M} = (\text{Q}, \text{I}, \Sigma, \rightarrow, \text{T})$ where:$\text{Q}$ is a finite set of states;$\text{I} \subseteq \...
293
views
0 answers
0 votes