
外部精选
软件工程
#社区热议用晚餐派对比喻讲解 Dirac 哈密顿回路定理的趣味证明
来源标题:Dirac's Theorem at a Dinner Party
一篇博客文章用假设的晚餐派对场景,重新梳理了 Gabriel Dirac 关于哈密顿回路的重要定理及其证明。文章还回顾了数十年来数学家如何将该定理推广到更广泛的图类,并提到下一篇将讨论 Barnette 猜想。Dirac 是物理学家 Paul Dirac 的继子。
Hacker Newsprideout2026/11/22 · 今天17 分钟阅读
以下正文由 AI 翻译自 Hacker News(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
It looks like the inline LaTeX got dropped in transit — every "has vertices", "at least neighbors", "that's potatoes" is missing its math. Here's the reconstruction, plus a few correctness notes on the proof itself.
Missing formulas
| Location | Should read |
|---|---|
| Dirac's theorem | If a simple graph has $n$ vertices ($n \ge 3$) and every vertex has at least $n/2$ neighbors, then the graph has a Hamiltonian cycle. |
| Party version | If a party has $n$ guests and every guest is friends with at least $n/2$ of the others, then the guests can sit at a round table so each sits between two friends. |
| Flip setup | Strangers $u,v$ sit side by side with $v$ just clockwise of $u$; elsewhere seatmates $x,y$ with $y$ just clockwise of $x$, where $x \sim u$ and $y \sim v$. Flip = reverse everyone from $v$ clockwise around to $x$. |
| Claim to prove | If $u,v$ are strangers, $v$ clockwise of $u$, and $d(u), d(v) \ge n/2$, then some friend $x$ of $u$ sits just counterclockwise of a friend $y$ of $v$. |
| Potatoes | $d(u)$ red + $d(v)$ Yukon Golds, which is at least $n$. Some guest holds two. |
| Lemma statement | After the flip, $u$ sits next to $x$ and $v$ sits next to $y$. |
Two spots where the lost variable matters for correctness:
- "note that u and v can no longer hold any potatoes" — it has to be both. $u$ passed its red potato clockwise and holds no gold ($u \nsim v$); $v$ passed its own gold and holds no red (same reason). With $n$ potatoes among $n-2$ guests, pigeonhole gives a double. Emptying only one of them gives $n$ potatoes among $n-1$ guests, which proves nothing.
- The guest with two potatoes has exactly one red and one gold (red potatoes land on distinct guests), so $w$ is a friend of $v$ and its red came from a friend of $u$ sitting counterclockwise of it — that's the crossing. Worth spelling out; otherwise "they have a Yukon Gold" reads like an assumption.
Other notes
- Termination isn't stated. The algorithm is a
whileloop, so readers will look for it: each flip closes the gap $uv$ and opens none (Lemma 1), so the gap count strictly decreases and the loop halts. One sentence after the algorithm. - The flip is well-defined because $u$ and $y$ lie outside the reversed block, so the block is a proper stretch. Cheap to note, and it's the kind of thing a careful reader will pick at.
- The potato argument is actually Ore's theorem, not Dirac's, and it's worth saying so: it only needs $d(u)+d(v) \ge n$ for the specific non-adjacent pair, which is exactly Ore's condition. Dirac is the symmetric special case where both degrees are $\ge n/2$. That also gives you a natural hook into the "each theorem is more general than the one to its left" figure (Dirac → Ore → Pósa → Bondy–Chvátal → Chvátal), which currently has no explanation in the text.
- Sharpness is unmentioned. $K_{n/2} \cup K_{n/2}$ has minimum degree $n/2 - 1$ and no Hamiltonian cycle, which pins down the constant. One line.
- Minor: use $\lceil n/2 \rceil$ rather than $n/2$ if you don't want to restrict to even $n$; and the "one from $v$ to the guest just clockwise of $x$" phrasing in the crossing definition would read better as "$v$ to $y$, the guest just clockwise of $x$."
I can't verify the interactive figures or the Dirac family anecdotes from here. If you wanted something else from this
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。