握手定理及其应用

设一个平面图G有n个顶点和m条边,我们称从每一个顶点所引出的边数为该点的度数。例如,图1中: 顶点V_1的度数记作d(v_1)=1。同理d(v_2)=4,d(v_3)=2,d(v_4)=3。显然有:sum from i=l to 4 d(v_i)