Children disliking in a circle $n\geq 3$ children are to be placed in a circle. Some pairs of children dislike each other and do not want to be next to each other. (Disliking is mutual.) What is the maximum $k$ such that if each child dislikes no more than $k$ other children, then a placement is always possible?
If a child dislikes $n-2$ other children, a placement is obviously not possible because we cannot find two children to be next to this child. If a child dislikes $n-3$ other children, his two neighbors are fixed.
 A: Consider the children as vertices of a graph, where an edge connects two children who like each other. Then the problem is reduced to finding a Hamiltonian cycle in this graph.
By Dirac's theorem, all $n$-vertex graphs whose minimum degree is at least $\left\lceil\frac n2\right\rceil$ are Hamiltonian. This translates to a maximum $k$ of
$$n-1-\left\lceil\frac n2\right\rceil=\left\lfloor\frac{n-2}2\right\rfloor$$
For example, if six children are such that each dislikes at most two others, we can always seat them around the table. If each dislikes three others, and the pattern of likes is as follows:
  A F
 /| |\
B | | E
 \| |/
  C D

then we cannot sit them around the table.
To show the sharpness of the bound for $k$ shown above, divide $n-1$ vertices into two sets $A$ and $B$ as equally as possible (so $|A|=\left\lceil\frac{n-1}2\right\rceil$ and $|B|=\left\lfloor\frac{n-1}2\right\rfloor$). Construct two graphs $K_{|A|}$ and $K_{|B|}$ and link the one remaining vertex to all the other vertices. The resulting graph has a maximal $k$ one more than the bound, but is non-Hamiltonian.
A: This is too long for a comment, but I think @parcly-taxel’s answer is incomplete. Dirac’s theorem translates to a maximum $k$ of at least $\lfloor\frac{n-2}{2}\rfloor$, not equal. To complete the argument, one must also show that there is no value of $n$ for which a seating is possible whenever there are at most $\lfloor\frac{n}{2}\rfloor$ dislikes per child.
Along the lines of Parcly’s example for $n=6$ and Henning’s comment on the initial question, there is no such $n$, because of the following counterexample:
Let the set of children be $\{a_1,\dots,a_{\lfloor\frac{n}{2}\rfloor},b_1,\dots,b_{\lfloor\frac{n}{2}\rfloor}\}\cup C$, where $C=\emptyset$ if $n$ is even and $C=\{c\}$ if $n$ is odd. Let the dislikes be the pairs $(a_i,b_j)$. The $a$ children must be adjacent, and so must the $b$ children, but the at most one other child $c$ (liked by all) can’t separate the $a$’s from the $b$’s at both ends.
