> A Hamiltonian cycle is a way to seat everyone at a round table so that each guest sits between two friends.
My mother, from a very WASPy family, would have hated a Hamiltonian cycle dinner party. She always sat couples and close friends apart, in order to stimulate the conversation. Now that I'm the adult, I don't dictate who sits where, but there is a small, judgy part of me that still cringes a little if a couple insists on sitting together.
I wonder if there's a similar theorem for an anti-Hamiltonian cycle. One where as few close connections as possible sit together.
Actually, as a middle school teacher who is always tweaking the seating plan to try and improve classroom management, that's not far from what I already do. (Must be shades of my mother in me.)
> A Hamiltonian cycle is a way to seat everyone at a round table so that each guest sits between two friends.
My mother, from a very WASPy family, would have hated a Hamiltonian cycle dinner party. She always sat couples and close friends apart, in order to stimulate the conversation. Now that I'm the adult, I don't dictate who sits where, but there is a small, judgy part of me that still cringes a little if a couple insists on sitting together.
I wonder if there's a similar theorem for an anti-Hamiltonian cycle. One where as few close connections as possible sit together.
Actually, as a middle school teacher who is always tweaking the seating plan to try and improve classroom management, that's not far from what I already do. (Must be shades of my mother in me.)
This is really nicely done.
The visualizations make the "flip" part of the argument immediately clear.
For the potato part, for me, an abstract verbal argument is clearer:
For any gap (u,v), mark all v neighbors, and all clockwise successors of all u neighbors.
n marks are now distributed among n-1 vertices (since v can't be marked). By pigeonhole, some vertex has 2 marks.
This is a really clever way of demonstrating Dirac's theorem.