Oreの定理の証明に関するメモ - Qiita

北大 井上先生の講義ノートを教科書としてグラフ理論を勉強中。 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