《离散数学》图论部分习题

《离散数学》图论部分习题1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2+6=92.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤63.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-14.求下图的补图.5.1)试画一个具有5个顶点的自补图2)是否存在具有6个顶点的自补图，试说明理由。对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整数，n=4k或n=4k+1，不存在6阶自补图。6.设图G为n(n2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n2且为奇数)，奇度点成对出现7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。8.图G如下图所示：1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{d(v)|vV}；κ(G)=min{|V’||V’是图G的点割集}；λ(G)=min{|E’||E’是图G的边割集}9.在什么条件下无向完全图Kn为欧拉图？n为奇数时10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数；桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？X+2*4+3*3=2*（2+3+x-1）x=913.证明：最大度Δ（T）≥k的树T至少有k片树叶。设有n个顶点，其中x片树叶2*（n-1）≥1*K+（n-x-1）*2+x*1x≥k14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1n=915.给出全部互不同构的4阶简单无向图的平面图形。16.如果G是平面图,有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.