17.如果U≥2,E<U,则连通图G至少有两个1度顶点。 18.令u和v是简单图G中的相邻顶点。证明:uv至少属于G中的d()+d(v)-U(G)个三角形。 19.证明含有n个顶点的k正则图有一条边。 20.证明:在k度正则图G中,kv≡0mod2),即正则图的阶数和度数不可能同时为奇数。( 21.证明:围长为4的k正则图至少含有2k个顶点;围长为5的k次正则图至少有k2+1个顶 22.证明:若G=(XUY,E)是一个k度正则二部图,则XHY|。 23.证明连通图中两条最长路必有公共顶点。 24.若G是简单图且(G)≥k,则G有长为至少k的路;如果k≥2,则G还包含一个长至少为k+1 的圈 25.每个无圈图G都有一个二部子图至少包含(G)条边。 26.证明:(a)E>v时,图中有圈。(b)E≥v+4时,图中有两个无公共边的圈。 27.证明:若G是δ(G)≥的简单图,则G是连通图。( 28.证明:(a)若e∈E(G),则o(G)≤o(G-e)≤(G)+1;(o(G)表示图G的连连同分支数)。 (b)若v∈(G),则o(G)≤o(G-v)≤O(G)+1未必成立,试举反例。 29.证明:若G是连通图,且每顶皆偶次,则o(G-v)≤-d(v)。 30.证明或反证:如果G是一个n顶点简单图,且其最大度是 2最小度是/ 2|-1,则G是连 通的 31.在一电路中,A,B两点间连接着一电阻,问至少要多少电阻,怎样连接,才能使得任意损坏9 个电阻时,A点与B点的电路仍连通且不短路? 32.证明G三H当且仅当G≡H。 33.证明:如果图G不连通,则其补图G必连通 34.如果图G满足G≡G,则称G是自补图。证明:若阶图G是自补图,则U=0,1(mod4)。 35.一个非连通简单图的补图一定是连通图吗?说明理由。 36.证明从一个8×8的方格棋盘中去掉对角的两个小方格后,不能被1×2和2×1的矩形覆盖 37.令G是一个4顶点图,删除其中的一个点后得到的子图系列如下,试确定G。17. 如果υ ≥ < 2, ε υ ，则连通图 G 至少有两个 1 度顶点。 18. 令 u 和 v 是简单图 G 中的相邻顶点。证明：u v 至少属于 G 中的 du dv G () () ( ) + −υ 个三角形。 19. 证明含有 n 个顶点的 k 正则图有 2 kn 条边。 20. 证明：在 k 度正则图 G 中，kν ≡ 0(mod 2)，即正则图的阶数和度数不可能同时为奇数。（ 21. 证明：围长为 4 的 k 正则图至少含有 2k 个顶点; 围长为 5 的 k 次正则图至少有 2 k +1个顶。 22. 证明：若G = (X ∪Y , E) 是一个 k 度正则二部图，则| X |=|Y |。 23. 证明连通图中两条最长路必有公共顶点。 24. 若 G 是简单图且δ (G) ≥ k ，则 G 有长为至少 k 的路；如果k ≥ 2 ，则 G 还包含一个长至少为 k +1 的圈。 25. 每个无圈图 G 都有一个二部子图至少包含 ( ) 2 ε G 条边。 26. 证明：(a) ε >ν 时，图中有圈。 (b) ε ≥ + ν 4 时，图中有两个无公共边的圈。 27. 证明：若 G 是 1 ( ) 2 G υ δ − ≥ 的简单图，则 G 是连通图。（ 28. 证明：(a) 若e EG ∈ ( ) ，则ω() ( ) ()1 G Ge G ≤ −≤ + ω ω ；（ω( ) G 表示图 G 的连连同分支数）。 (b) 若v VG ∈ ( ) ，则ω() ( ) ()1 G Gv G ≤ −≤ + ω ω 未必成立，试举反例。 29. 证明：若 G 是连通图，且每顶皆偶次，则 1 ( ) () 2 ω G v dv − ≤ 。 30. 证明或反证：如果 G 是一个 n 顶点简单图，且其最大度是 2 ⎡n ⎤ ⎢ ⎥ ⎢ ⎥ 、最小度是 1 2 ⎡ ⎤ n − ⎢ ⎥ ⎢ ⎥ ，则 G 是连 通的。 31. 在一电路中，A，B 两点间连接着一电阻，问至少要多少电阻，怎样连接，才能使得任意损坏 9 个电阻时，A 点与 B 点的电路仍连通且不短路？ 32. 证明G H≅ 当且仅当G H≅ 。 33. 证明：如果图 G 不连通，则其补图G 必连通。 34. 如果图 G 满足G G≅ ，则称 G 是自补图。证明：若υ 阶图 G 是自补图，则υ = 01 4 , (mod ) 。 35. 一个非连通简单图的补图一定是连通图吗？说明理由。 36. 证明 从一个8 8 × 的方格棋盘中去掉对角的两个小方格后，不能被1 2 × 和 2 1× 的矩形覆盖。 37. 令 G 是一个 4 顶点图，删除其中的一个点后得到的子图系列如下，试确定 G