精选优质文档-倾情为你奉上习题十1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v) n-1, G图的总点度上限为 max(d(v) nmax(d(v) n(n-1) 。根据握手定理，G图边的上限为 max(m) n(n-1)/2,所以。（2） =G是完全图因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。G是完全图 =因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）3。证明：反证法，假设,则G的总点度上限为max(d(u) 2 n，根据握手定理，图边的上限为max(m) 2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）
