北大 井上先生の講義ノートを教科書としてグラフ理論を勉強中。
Oreの定理の証明がよくわからなかったので調べていたところ、motchy氏のわかりやすい証明を見つけたのだが、一箇所難しいところがあったのでメモを残す。
https://motchy99.blog.fc2.com/blog-entry-40.html
然るに定理の仮定から$n(A)+n(B) \ge n$であるので$A$と$B$は共通部分を持つ,すなわち、ある$i (0 \le i \le k-1)$が存在して$u_i$は$u_k$の隣接接点で、$u_{i+1}$は$u_0$の隣接接点である。
(太字強調は筆者による)
に関しては、太字部分が仮に成立しないとすると、Bに含まれる点はAの点の隣には置けないので、$n(A)$個だけ候補となる点が減って、$n(B) \le k-n(A)$となる。一方で$n(A)+n(B) \ge n \ge k+1$より$n(B) \ge k-n(A)+1$であるから矛盾するため、太字部分は成り立つ。