Xu《图论》1.3习题1.3.2.证明任何v(≥2)阶简单无向图总存在顶点度相等的两顶点。证明设图中所有顶点的度从小到大排序为d1,d2,…,dv由于dv≤v−1故0≤d1,d2,…,dv≤v−1即这v个整数介于0到v-1之间如果没有两个数相同则v个数分别取到了0~v-1但不可能同时有d10且dvv−1。因此必有两个数相同证毕。