第一章习题υ(1)υ−υ(1)υ−1.对任何简单图G，(1)证明：ε()G≤；(2)ε()G=当且仅当GK≅。22νυ22.证明：(1)ε()Kmn=；(2)若G是完全二部图，则ε()G≤。mn,43.图G有21条边，12个3度顶点，其余顶点的度均为2，求图G的阶数。4.证明：任何简单图必有至少两个顶点具有相等的度。5.设G是简单图，求G的所有不同的生成子图的个数（包括G本身和空图）。6.证明：任何图中，奇度顶点的个数总是偶数（包括0）。并由此证明：在任一次聚会上握过奇数次手的人必为偶数个。7.证明或反证：如果u和v是图G中仅有的具有奇数度的顶点，则G包含一条u,v路。8.证明：若υ≥4且ε=ν+1，则存在v∈V(G)使得d(v)≥3。由此证明：n个球队比赛（n≥4），已赛完n+1场，则必定有一个球队已参加过至少3场比赛。9.在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有13个队，能否恰当安排比赛使得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛？10.在平面上有n个点Sxxx=⋅⋅⋅{,12,,n}，其中任两个点之间的距离至少是1。证明在这n个点中，距离为1的点对数不超过3n。11.某次会议有n人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。12.在一个化学实验室里，有n个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这n个药箱中共有几种不同的化学品？13.在一次舞会中，A、B两国留学生各nn(2)>人，A国每个学生都与B国一些(不是所有)学生跳过舞，B国每个学生至少与A国一个学生跳过舞。证明一定可以找到A国两个学生aa12,及B国两个学生bb12,，使得a1和ba12,和b2跳过舞，而a1和ba22,和b1没有跳过舞。2ε2ε14.证明：δ≤≤Δ，（其中称为顶点平均度）。υυ15.令G是至少有两个顶点的图。证明或反证：(1)删除一个度为Δ()G的顶点不会增加顶点的平均度；(2)删除一个度为δ()G的顶点不会减小顶点的平均度。2ε16.令G是一个顶点平均度为a=的无圈图。(1)证明：Gx−的顶点平均度至少为a当且仅当υaadx()≤。(2)利用(1)的结果给出一个算法来证明：如果a>0，则G有一个最小度大于的22子图。17.如果υ≥<2,ευ，则连通图G至少有两个1度顶点。18.令u和v是简单图G中的相邻顶点。证明：uv至少属于G中的du()+dv()−υ(G)个三角形。kn19.证明含有n个顶点的k正则图有条边。220.证明：在k度正则图G中，kν≡0(mod2)，即正则图的阶数和度数不可能同时为奇数。（21.证明：围长为4的k正则图至少含有2k个顶点;围长为5的k次正则图至少有k2+1个顶。22.证明：若G=(X∪Y,E)是一个k度正则二部图，则|X|=|Y|。23.证明连通图中两条最长路必有公共顶点。24.若G是简单图且δ(G)≥k，则G有长为至少k的路；如果k≥2，则G还包含一个长至少为k+1的圈。ε()G25.每个无圈图G都有一个二部子图至少包含条边。226.证明：(a)ε>ν时，图中有圈。(b)ε≥+ν4时，图中有两个无公共边的圈。υ−127.证明：若G是δ()G≥的简单图，则G是连通图。（228.证明：(a)若eEG∈()，则ω()GGeG≤−≤+ωω()()1；（ω()G表示图G的连连同分支数）。(b)若vVG∈()，则ω()GGvG≤−≤+ωω()()1未必成立，试举反例。129.证明：若G是连通图，且每顶皆偶次，则ω()Gv−≤dv()。2⎡n⎤⎡⎤n30.证明或反证：如果G是一个n顶点简单图，且其最大度是、最小度是−1，则G是连⎢2⎥⎢⎥2通的。31.在一电路中，A，B两点间连接着一电阻，问至少要多少电阻，怎样连接，才能使得任意损坏9个电阻时，A点与B点的电路仍连通且不短路？32.证明GH≅当且仅当GH≅。33.证明：如果图G不连通，则其补图G必连通。34.如果图G满足GG≅，则称G是自补图。证明：若υ阶图G是自补图，则υ=01,(mod)4。35.一个非连通简单图的补图一定是连通图吗？说明理由。36.证明从一个88×的方格棋盘中去掉对角的两个小方格后，不能被12×和21×的矩形覆盖。37.令G是一个4顶点图，删除其中的一个点后得到的子图系列如下，试确定G。38.下面两图是否同构？