运筹学讲义 §2.1.1图的基本概念(1) 图( graph):用(顶)点代表对象,顶点之间的边表示对象之间的关系 滨州 “图是关系的数学表达” 齐南 注:图和几何图形不同.几何图形描述物体 青岛 的形状和结构:图仅反映对象之间的关系 聊城 图中顶点的相对位置,顶点之间的边的长短 粗细对反映对象之间的关系并不重要.如 角形两边之和大于第三边”等几何定理 枣庄 在图论中不再成立 图的表示:G=(V,E),其中V为顶点集,E为边集一般地,要求V≠Φ,但E无此要求 顶点( vertex,结(节)点,node):v∈V;边(edge):e=nv∈E;端点( endpoint):l,p 顶点数:v=1:边数:E= 边数E称为图的规模(sie) 注:集合的阶( cardinality):S=集合S中含有的元素的个数 种关系:顶点与顶点相邻(邻接)( adjacent);边与边相邻(邻接);顶点与边关联( incident 有限图( finite graph):v<+o,E<+o 无限图( infinite graph): otherwise 注:以后如不加说明,在本课程中出现的图总是指有限图 空图( empty graph):l≤v<+∞,E=0; 非空图( nonempty graph): otherwise 平凡图( trivial graph):v=1,E=0 非平凡图( nontrivial graph): otherwise. 连杆(link):两个端点不重合的边 环(loop):两个端点重合的边 重边( multiedge,平行边, parallel edge): several edges with the same two distinct endpoints
运 筹 学 讲 义 1 §2.1.1 图的基本概念(1) 图 图（graph）：用（顶）点代表对象，顶点之间的边表示对象之间的关系. “图是关系的数学表达”. 注：图和几何图形不同.几何图形描述物体 的形状和结构；图仅反映对象之间的关系， 图中顶点的相对位置，顶点之间的边的长短 粗细对反映对象之间的关系并不重要.如 “三角形两边之和大于第三边”等几何定理 在图论中不再成立. 图的表示： G = (V, E) ，其中 V 为顶点集， E 为边集.一般地，要求 V ，但 E 无此要求. 顶点(vertex，结(节)点，node)： vV ；边(edge)：e = uvE ；端点(endpoint)：u, v . 顶点数： = V ；边数： = E . 边数 称为图的规模（size）. 注：集合的阶（cardinality）： S = 集合 S 中含有的元素的个数. 三种关系：顶点与顶点相邻（邻接）（adjacent）；边与边相邻（邻接）；顶点与边关联（incident）. 有限图（finite graph）： +, + ； 无限图（infinite graph）：otherwise. 注：以后如不加说明，在本课程中出现的图总是指有限图. 空图（empty graph）： 1 +, = 0 ； 非空图（nonempty graph）：otherwise. 平凡图（trivial graph）： = 1, = 0 ； 非平凡图（nontrivial graph）：otherwise. 连杆（link）：两个端点不重合的边； 环（loop）：两个端点重合的边； 重边（multiedge，平行边，parallel edge）：several edges with the same two distinct endpoints
运筹学讲义 连杆 环 重边 注:以后如不加说明,“边”总是指连杆. 简单图( simple graph):不含有重边和环的图; 重图( multigraph):不含有环(可含有重边)的图 显然,若图G是简单图,则E≤C2(何时取等号?) PFTa R(plane graph): a graph any two edges of which intersect only at their endpoint 非平面图( nonplane graph): otherwise. 平面图 非平面图 可平面图( planar graph): a graph which can be drawn in a plane(平面) so that any two edges of it intersect only at their endpoints 非可平面图( nonplanar graph): otherwis 可平面图 非可平面图 注:一个非平面图有可能是可平面图! 权( weight):给每条边以一个数字(如距离,长度,流量,费用等) 赋权图( weighted graph):边带有权的图 无向图( graph):边无方向的图 有向图( digraph, directed graph): otherwise. 混合图( mixed graph):有的边有方向,有的边无方向的图 注:以后如不加说明,“图”无向图 图的同构( graphic isomorph i sm) 定义对图G1,G2,若彐一一映射( bi jection)f:(G1)→V(G2),使得
运 筹 学 讲 义 2 注：以后如不加说明，“边”总是指连杆. 简单图（simple graph）：不含有重边和环的图； 重图（multigraph）：不含有环（可含有重边）的图. 显然，若图 G 是简单图，则 2 C （何时取等号？）. 平面图（plane graph）：a graph any two edges of which intersect only at their endpoints； 非平面图（nonplane graph）：otherwise. 可平面图（planar graph）：a graph which can be drawn in a plane(平面) so that any two edges of it intersect only at their endpoints； 非可平面图（nonplanar graph）：otherwise. 注：一个非平面图有可能是可平面图！ 权（weight）：给每条边以一个数字（如距离，长度，流量，费用等）； 赋权图（weighted graph）：边带有权的图. 无向图（graph）：边无方向的图； 有向图（digraph，directed graph）：otherwise. 混合图（mixed graph）：有的边有方向，有的边无方向的图． 注：以后如不加说明，“图”无向图. 图的同构（graphic isomorphism） 定 义 对 图 1 2 G ,G ， 若 一一映射（ bijection ） : ( ) ( ) V G1 V G2 f → ，使得
运筹学讲义 vv∈(G1),∈E(G1),有f(u)f(v)∈E(G2),则称G1与G2同构( isomorphic),记作G1=G2 简言之,两个图的结构完全一样即同构 f:a>4,b→>2,c→>1 d→3,e→>5 同构的两个图 不同构的两个图 三 K4的同构图 当图的规模较大时,判断图是否同构很困难. 注:(1)同构是图的一种等价关系,具有反身性,对称性和传递性 (2)同构的两个图有相同的顶点数和边数,反之不真:顶点数或边数不相同的两个图不可能同 构.如 (3)同构关系保持图的对应顶点的度和邻接性 (4)任一v个顶点的简单图必同构于K的某一子图 例1(1)试画出顶点数为3的所有不同构的简单图. (2)试画出顶点数为4的所有不同构的简单图 解:(1)顶点数为3的不同构的简单图共有4个,分别为
运 筹 学 讲 义 3 , ( ), ( ) V G1 uv E G1 u v ，有 ( ) ( ) ( ) E G2 f u f v ，则称 G1 与 G2 同构（isomorphic），记作 G1 G2 . 简言之，两个图的结构完全一样即同构. 同构的两个图 3, 5 : 4, 2, 1, → → → → → d e f a b c 当图的规模较大时，判断图是否同构很困难. 注：（1）同构是图的一种等价关系，具有反身性，对称性和传递性. （2）同构的两个图有相同的顶点数和边数，反之不真；顶点数或边数不相同的两个图不可能同 构.如 （3）同构关系保持图的对应顶点的度和邻接性. （4）任一 个顶点的简单图必同构于 K 的某一子图. 例 1（1）试画出顶点数为 3 的所有不同构的简单图. （2）试画出顶点数为 4 的所有不同构的简单图. 解：（1）顶点数为 3 的不同构的简单图共有 4 个，分别为
运筹学讲义 (2)顶点数为4的不同构的简单图共有11个,分别为 E≤C4=6 E=3 E=5 E=6 若干特殊的图 完全(完备)图( complete graph):任两个互异顶点之间均恰好有唯一一条边相连的图 表示:K △区 K 注:由完全图的定义易见,在顶点数相同的所有简单图中,K,的边数最多,且边数为C2
运 筹 学 讲 义 4 （2）顶点数为 4 的不同构的简单图共有 11 个，分别为 6 2 C4 = = 0 =1 = 2 = 3 = 4 = 5 = 6 若干特殊的图 完全（完备）图（complete graph）：任两个互异顶点之间均恰好有唯一一条边相连的图. 表示： K . 注：由完全图的定义易见，在顶点数相同的所有简单图中， K 的边数最多，且边数为 2 C
运筹学讲义 性质:若G是简单图,则(1)E≤C2:(2)E=C2分G是完全图 证明:(1)注:(2)显然.→∵5(K,)=C,若G不是完全图,则由(G)=C知,G必 含有环或重边,与G是简单图矛盾 例2有n个药箱,每两个药箱恰好装有一种相同的药,每种药也恰好装在两个药箱里,问有多少 种药? 解:以n个药箱为顶点,两个顶点之间有一条边相连当且仅当两个药箱有一种相同的药,作完全 图Kn∴药的种数=s(Kn)=C2■ 分(部)图(偶图, bipartite graph):G=(X,Y)s.t.X∪Y=V,X∩Y=Φ,E:X←>Y v=5的不同构的连通的二分图共有5个: 一般地,规定二分图为简单图 例4一个二分图:3-方体图(3-cube) 注:k一方体(k-cube) Thek- cube is the graph whose vertices are the ordered k- tuples(有序k元组)of0sand1's, wo vertices being joined if and only if they differ in exactly one coordinate(坐标,分量)
运 筹 学 讲 义 5 性质：若 G 是简单图，则（1） 2 C ；（2） = C 2 G 是完全图. 证明：（1）注；（2） 显然. 2 ( ) Kp = C ，若 G 不是完全图，则由 2 ( ) G = C 知， G 必 含有环或重边，与 G 是简单图矛盾.▌ 例 2 有 n 个药箱，每两个药箱恰好装有一种相同的药，每种药也恰好装在两个药箱里，问有多少 种药？ 解：以 n 个药箱为顶点，两个顶点之间有一条边相连当且仅当两个药箱有一种相同的药，作完全 图 Kn . 药的种数 ( ) Kn = 2 = Cn .▌ 二分（部）图（偶图，bipartite graph）： G = (X ,Y) s.t. X Y = V, X Y = ，E : X Y . = 5 的不同构的连通的二分图共有 5 个： 一般地，规定二分图为简单图. 例 4 一个二分图：3-方体图（3-cube） ▌ 注： k −方体（ k −cube） The k −cube is the graph whose vertices are the ordered k −tuples（有序 k 元组） of 0’s and 1’s， two vertices being joined if and only if they differ in exactly one coordinate（坐标，分量）. e.g
运筹学讲义 0,0,1)g 0,1,D) 0,1)9 1,0,1) q,1) ,0) 0,1,D) 0,0) 1,0) 00) ,1,0) 性质k-方体是二分图,且E=2k,E=k·2k-1 证明:由k一方体的定义可知,k-方体的顶点与分量取值为0,1的k维向量一一对应.故k一方 体的顶点数p=分量取值为0,1的k维向量的个数=22…2=2 k一方体的一个顶点v,ν对应某一个分量取值为0,1的k维向量ν.显然,与向量v仅有 个分量不相同的分量取值为0,1的k维向量恰有k个,即与顶点v相关联的边的条数为k.又k一方 体的每一条边都关联两个顶点,故k-方体的边数E、k.24 k 按照每一个顶点对应的分量取值为0,1的k维向量的各分量的和的奇偶性,将k一方体的所有 顶点分为奇、偶两个部分.显然,每一部分的顶点之间没有边相连,故k一方体是二分图. 完全二分图( complete bipartite graph): a simple bipartite graph G=(X,Y) in which each vertex of X is joined to each vertex of Y, where x=m, r n, m+n=v 表示:Kmn 风A以 3,3 例4一个完全二分图
运 筹 学 讲 义 6 性质 k −方体是二分图，且 1 2 , 2 − = = k k k . 证明：由 k −方体的定义可知， k −方体的顶点与分量取值为 0，1 的 k 维向量一一对应.故 k − 方 体的顶点数 p = 分量取值为 0，1 的 k 维向量的个数 = k k 2 2 2 = 2 个 . k −方体的一个顶点 v， v 对应某一个分量取值为 0，1 的 k 维向量 v.显然，与向量 v 仅有一 个分量不相同的分量取值为 0，1 的 k 维向量恰有 k 个，即与顶点 v 相关联的边的条数为 k .又 k − 方 体的每一条边都关联两个顶点，故 k −方体的边数 1 2 2 2 − = = k k k k . 按照每一个顶点对应的分量取值为 0，1 的 k 维向量的各分量的和的奇偶性，将 k − 方体的所有 顶点分为奇、偶两个部分.显然，每一部分的顶点之间没有边相连，故 k − 方体是二分图.▌ 完全二分图（complete bipartite graph）：a simple bipartite graph G = (X ,Y) in which each vertex of X is joined to each vertex of Y ，where X = m， Y = n ，m + n = . 表示： K m,n . 例 4 一个完全二分图：
运筹学讲义 2 性质:(1)(Kmn)=mn;(2)若G是二分图,则E(G)≤;且E(G) 证明:(1)由完全二分图的定义 (2)设G=(X,Y),X=m,P=n,m+n=v,则 E(G)≤E(k m)=m5(+n)2=(5)=4 由(2)知,E(G)=4/(O)=6(Km)mG≡Km 三K m=n 星(sar):K1n 星是一种重要的完全二分图,常用来研究计算机网络,星的度为n的顶点表示网络服务器 server),其余n个顶点表示计算机( computer) 顶点的度 顶点的度(次, degree):d(v)= the number of edges of a graph G incident with v( each loop is counted as two edges 最小度( minimum degree):δ=mn{d(v) 最大度( maximum degree):△=max{a(v)} 奇顶点(od- degree vertex); a vertex whose degree is odd 偶顶点(even- degree vertex): a vertex whose degree is even 悬挂点( suspended vertex): a vertex with the degree 1 悬挂边( suspended edge): a edge incident with the suspended verte 7
运 筹 学 讲 义 7 ▌ 性质：（1） (K m,n ) = mn ；（2）若 G 是二分图，则 4 ( ) 2 G ；且 2 , 2 2 4 ( ) G = G K . 证明：（1）由完全二分图的定义； （2）设 G = (X ,Y) ， X = m， Y = n ， m + n = ，则 4 ) 2 ) ( 2 ( ) ( ) ( 2 2 2 , = = + = m n G K m n mn ； 由（2）知， 2 , 2 , , 2 2 ( ) ( ) 4 ( ) G K m n G K m n G K G m n m n m n = = = = = + = .▌ 星（star）： K1,n 星是一种重要的完全二分图，常用来研究计算机网络，星的度为 n 的顶点表示网络服务器 （server），其余 n 个顶点表示计算机（computer）. 顶点的度 顶点的度（次，degree）： dG (v) = the number of edges of a graph G incident with v （each loop is counted as two edges）. 最小度（minimum degree）： min {d(v)} vV = ； 最大度（maximum degree）： max{d(v)} vV = . 奇顶点（odd-degree vertex）：a vertex whose degree is odd； 偶顶点（even-degree vertex）：a vertex whose degree is even. 悬挂点（suspended vertex）：a vertex with the degree 1. 悬挂边（suspended edge）：a edge incident with the suspended vertex
运筹学讲义 孤立点( isolated vertex): a vertex with the degree o. 注:(1)另一种表示方法:d(v)=deg(v) (2)v∈,d(v)≥0,d≤d(v)≤△ (3)若G是简单图,则d()≤v-1;当然,δ,△≤v-1. (4)若G是简单图,且δ=v-1,则G=K (5)对二分图G=(X,y),有∑4()=∑()=E k-iEAL (regular graph ) a graph all vertices of which have the same degree k 如K.,Kn,分别为v-1-正则图,n-正则图,k一方体是k一正则图 显然,若δ=Δ,则G为正则图 例5求证:若G=(X,Y)是正则二分图,则X|=|X 证明:不妨设G是k一正则图,则由正则图的定义和顶点的度的定义的注(5)有 k|X=∑(v)=E=∑4(v)=k| YHXEY v∈X 例6求证:若G为简单图,且v≥2,则G中至少有两个顶点的度数相等. 证明:W.L.O.G.G中无孤立点,(反证法)假设G中各顶点的度数均不相等,则G中各顶点的 度数为1,2,3,…,v-1,v,于是△=v;但由G为简单图知,△≤v-1,矛盾 另证:W.L.O.G.设G为简单图,且不含有孤立点,则δ≥1,△≤v-1 (反证法)假设G中的各顶点的度均不相等,则v(O)≤△-6+1≤(v-1)+1=v,矛盾 直观解释:v-1,v-2,…,2,1,共v-1≤v个顶点l 例7求证:在任一不少于两个人的人群中,必至少有两个人有相同个数的朋友 证明:以人为顶点,两个顶点之间有边相连当且仅当两个人是朋友,作图G 显然,G为简单图,且v≥2,故由例7知结论成立. Th1(图论第一定理,欧拉定理)∑d()= (The sum of degrees of all the vertices is twice of the number of edges in any graph Proof: Each edge is incident with two vertices( its two endpoints), therefore is counted twice in Corollary(握手定理) In any graph, the number of odd- degree vertices is even Proof: Let VI=fodd-degree vertices), V2=feven-degree vertices hen2E=∑(v)=∑()+∑d()(e) Since 2d(v)is even, 2d(v)is even: By definition of K,l is even.I
运 筹 学 讲 义 8 孤立点（isolated vertex）：a vertex with the degree 0. 注：（1）另一种表示方法： d(v) = deg(v) . （2） v V ， d(v) 0， d(v) . （3）若 G 是简单图，则 d(v) −1 ；当然， , −1. （4）若 G 是简单图，且 = −1 ，则 G = K . （5）对二分图 G = (X ,Y) ，有 = = vX vY d(v) d(v) . k −正则图（regular graph）：a graph all vertices of which have the same degree k . 如 K， Kn,n 分别为 −1−正则图， n −正则图，k −方体是 k − 正则图. 显然，若 = ，则 G 为正则图. 例 5 求证：若 G = (X ,Y) 是正则二分图，则 | X |=| Y | . 证明：不妨设 G 是 k −正则图，则由正则图的定义和顶点的度的定义的注（5）有， k | X | d(v) d(v) k | Y | | X | | Y | v X v Y = = = = = .▍ 例 6 求证：若 G 为简单图，且 2 ，则 G 中至少有两个顶点的度数相等. 证明：W.L.O.G. G 中无孤立点，（反证法）假设 G 中各顶点的度数均不相等，则 G 中各顶点的 度数为 1,2,3, , −1, ，于是 = ；但由 G 为简单图知， −1 ，矛盾. 另证：W.L.O.G.设 G 为简单图，且不含有孤立点，则 1, −1. （反证法）假设 G 中的各顶点的度均不相等，则 (G) − +1 ( −1) +1 = ，矛盾. 直观解释： −1, − 2, ,2,1 ，共 −1 个顶点.▍ 例 7 求证：在任一不少于两个人的人群中，必至少有两个人有相同个数的朋友. 证明：以人为顶点，两个顶点之间有边相连当且仅当两个人是朋友，作图 G . 显然， G 为简单图，且 2 ，故由例 7 知结论成立.▍ Th1（图论第一定理，欧拉定理） ( ) = 2 vV d v . （The sum of degrees of all the vertices is twice of the number of edges in any graph） Proof：Each edge is incident with two vertices(its two endpoints),therefore is counted twice in .▍ Corollary（握手定理）In any graph，the number of odd-degree vertices is even. Proof: Let V1 = {odd-degree vertices}, V2 = {even-degree vertices}. Then = = + 1 2 2 ( ) ( ) ( ) v V v V v V d v d v d v (even!). Since 2 ( ) v V d v is even， 1 ( ) v V d v is even；By definition of V1 ， V1 is even.▍
运筹学讲义 Note:“握手定理”的由来:某次宴会上,熟人见面互相握手.求证:握过奇数次手的人的个数必 为偶数 证明:以人为顶点,两个顶点之间有边相连当且仅当两个人握过手,作图G 由 Corollary知,G中奇顶点的个数为偶数,即握过奇数次手的人有偶数个■ 例8某次宴会上,共有28769个人.熟人见面互相握手.求证:若每个人都至少握手一次,则其中 必至少有1人至少握手两次 证明:以人为顶点,两个顶点之间有边相连当且仅当两个人握过手,作图G.于是,问题分求 证G中至少存在一个度数超过2的顶点 (反证法)假设G中不存在度数超过2的顶点,则由每个人都至少握手一次知,G中每个顶点 的度数都恰为1.即G的全部28769(奇数!)个顶点的度数都是1,与 Corollary矛盾.l 例8(续)某次学术会议有263人参加每人至少和3个人讨论一次.求证:至少有1人和4人以 上讨论过 证:反证法. 例9求证:δ≤一≤△. 证明:vs∑(v)=2≤△·v→6≤≤△.l 例10求证:若G为k一正则图,则k 证明:2E=∑d()=kv→k= 例11求证:若图G中无孤立点,且E≤v-1,则G中至少有一个悬挂点 证明:(反证法)假设G中无悬挂点,则2E=∑4()≥2v→E≥v.矛盾 注:(1)(逆否命题)若图G中无孤立点和无悬挂点,则E≥v-1 (2)条件“G中无孤立点”可增强为“G是连通图”,结论仍成立 例12图的各顶点的度按不增顺序排成的序列称为图的度序列( degree sequence).问以下数列能 否为某简单图的各顶点的度序列? (1)1,1,2,3,2:(2)7,6,5,4,3,3,2:(3)6,6,5,4,3,3,1(4)5,4,2,2, 2,1,1:(5)10,6,3,2,2,1,1,1 解:(1)不能.∵奇顶点的个数为3:(2)不能.∵P=7,d(v)≤p-1=6 (3)假设此数列是图G的度序列,d(v)=d(v2)=6,d(v)=1,p=7,∴V必和其余6 个顶点均相邻;同理,V2也必和其余6个顶点均相邻故d(v7)≥2,矛盾 (4)不能.∵奇顶点的个数为3:(5)不能∵P=8,d(v)≤8-1=7
运 筹 学 讲 义 9 Note：“握手定理”的由来：某次宴会上，熟人见面互相握手.求证：握过奇数次手的人的个数必 为偶数. 证明：以人为顶点，两个顶点之间有边相连当且仅当两个人握过手，作图 G . 由 Corollary 知， G 中奇顶点的个数为偶数，即握过奇数次手的人有偶数个.▍ 例 8 某次宴会上，共有 28769 个人.熟人见面互相握手.求证：若每个人都至少握手一次，则其中 必至少有 1 人至少握手两次. 证明：以人为顶点，两个顶点之间有边相连当且仅当两个人握过手，作图 G .于是，问题 求 证 G 中至少存在一个度数超过 2 的顶点. （反证法）假设 G 中不存在度数超过 2 的顶点，则由每个人都至少握手一次知， G 中每个顶点 的度数都恰为 1.即 G 的全部 28769（奇数！）个顶点的度数都是 1，与 Corollary 矛盾.▍ 例 8（续）某次学术会议有 263 人参加.每人至少和 3 个人讨论一次.求证：至少有 1 人和 4 人以 上讨论过. 证：反证法.▍ 例 9 求证： 2 . 证明： = 2 ( ) 2 v V d v .▍ 例 10 求证：若 G 为 k −正则图，则 2 k = . 证明： 2 2 = ( ) = = d v k k v V .▍ 例 11 求证：若图 G 中无孤立点，且 −1 ，则 G 中至少有一个悬挂点. 证明：（反证法）假设 G 中无悬挂点，则 = 2 ( ) 2 v V d v .矛盾.▍ 注：（1）（逆否命题）若图 G 中无孤立点和无悬挂点，则 −1. （2）条件“ G 中无孤立点”可增强为“ G 是连通图”，结论仍成立. 例 12 图的各顶点的度按不增顺序排成的序列称为图的度序列（degree sequence）.问以下数列能 否为某简单图的各顶点的度序列？ （1）1，1，2，3，2；（2）7，6，5，4，3，3，2；（3）6，6，5，4，3，3，1（4）5，4，2，2， 2，1，1；（5）10，6，3，2，2，1，1，1. 解：（1）不能. 奇顶点的个数为 3；（2）不能. p = 7 ，d(v) p −1 = 6 ； （3）假设此数列是图 G 的度序列， d(v1 ) = d(v2 ) = 6，d(v7 ) = 1， p = 7 ， 1 v 必和其余 6 个顶点均相邻；同理， 2 v 也必和其余 6 个顶点均相邻.故 d(v7 ) 2 ，矛盾； （4）不能. 奇顶点的个数为 3；（5）不能. p = 8 ，d(v) 8 −1 = 7 .▍
运筹学讲义 例13问以下数列能否是某简单图的各顶点的度序列?如是,请画出图 (1)5,3,2,2,1,1:(2)4,4,3,2,2,1:(3)2,1,1,0. 解 例14求证:若图G有n个顶点,n+1条边,则G中至少有一个顶点的度不小于3 证明:(反证法)假设G中所有顶点的度都小于3(即≤2),则 2(n+1)=26=∑d(v)s2n→n+1≤n,矛盾
运 筹 学 讲 义 10 例 13 问以下数列能否是某简单图的各顶点的度序列？如是，请画出图. （1）5，3，2，2，1，1；（2）4，4，3，2，2，1；（3）2，1，1，0. 解： ▍ 例 14 求证：若图 G 有 n 个顶点， n +1 条边，则 G 中至少有一个顶点的度不小于 3. 证 明 ：（ 反 证 法 ） 假 设 G 中所有顶点的度都小于 3 （ 即 2 ）， 则 n d v n n n v V + = = + 2( 1) 2 ( ) 2 1 ，矛盾.▍