看到网上有博客说, 一个 nnn 个点 mmm 条边的无向图,把度数小于 m\sqrt mm 的点记为轻点,把度数大于等于 m\sqrt mm 的点记为重点,那么一个轻点只与不超过 m\sqrt mm 个点相邻,一个重点只与不超过 m\sqrt mm 个重点相邻。
这个怎么证明?我试了下,假设 uuu 这个重点与 m\sqrt mm 个重点相邻,与它相邻的重点度数都大于等于 m\sqrt mm,那么总度数至少为 m×m+m=m+m\sqrt m\times \sqrt m+\sqrt m=m+\sqrt mm×m+m=m+m,仍然小于 2m2m2m。