Dirac's Theorem at a Dinner Party

(prideout.net)

12 points | by prideout 2 hours ago ago

2 comments

  • jonahx 43 minutes ago ago

    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.

  • pepy07 36 minutes ago ago

    This is a really clever way of demonstrating Dirac's theorem.