度 (图论) 在图论中一个顶点在图中的度 degree为与这个顶点相连接的边的数目在多重图中自环被计数两次 顶点 v displaystyle v 的度记作 deg   v  displaystyle degv 或 deg  v displaystyle deg v 图G的最大度记作ΔG最小度记作δG分别为图中所有顶点度的最大值和最小值 在右边的多重图中最大度为最小度为 在正则图中所有度都是相同的因为我们可以直接说该图的度是多少 完全图是正则图中的一种特殊情况其任意两个点均相连若顶点数为p则该图的度为p 给定一个图 G   V  E  displaystyle GVE 其度求和公式为  v  V deg   v     E   displaystyle sum vin VdegvE 该公式表明在任意无向图中度为奇数的顶点的个数为偶数即为握手定理该定理名称来自于一个热门的数学问题即证明在一个团体中与他人握手奇数次的人的数量为偶数个 对于有向图 节点顶点的入度是指进入该节点顶点的边的条数 节点顶点的出度是指从该节点顶点出发的边的条数