3
$\begingroup$

There is a bunch of $n$ people. Everyone is friends with 3 other people in this bunch. They want to have breakfast seated around a round table, but, they are wanting to sit next to their friends. Then, for each pair of friends, the number of seating possibilities in which they sit next to each other, is an even number.

$\endgroup$
3
$\begingroup$

The question is equivalent to the following graph-theoretic question:

Let $G$ be a $3$-regular graph, and let $e$ be an edge of $G$; then the number of Hamilton cycles containing $e$ is even.

I'll leave this reformulation here as a hint. This is a special case of a more general theorem: it's enough to assume that each vertex has odd degree. That theorem is proved in the answer to this question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.