圖論握手定理：無向圖頂點度數之和與邊數關系 e = d/2 的證明與應用

定理陳述

無向圖中所有頂點度數之和 d 等於邊數 e 的兩倍：d = 2e，即 e = d/2。

證明

每條邊連接兩個頂點，為兩端點各貢獻 1 度。遍歷所有邊，總貢獻為 2e，即所有頂點度數之和。

示例驗證

三角形圖（3 頂點、3 邊）：每頂點度數 2，度數和 d = 6，邊數 e = 3，滿足 e = d/2。

應用場景

• 快速驗證圖數據合法性：度數和必為偶數。
• 推導圖的平均度：d_avg = 2e/n。
• 證圖中奇度頂點個數為偶數（握手定理推論）。

總結

握手定理是圖論最基礎、最實用的結論之一，連接局部屬性（度數）與全局屬性（邊數），是圖算法分析的起點工具。