第五章支配集、独立集、覆盖集和 Ramsey数 本章讨论图中具有某种特性的顶点子集和边子集,以及它们之间的关系。本章所讨论的 图均为简单图。 §5.1支配集、点独立集、点覆盖集 、支配集( Domination set) 定义511设DcH(G),若对v∈V(G),要么u∈D,要么u与D中的某些顶点相邻 则称D为图G的一个支配集。如果一个支配集的任何真子集都不是支配集,则称它为极小支 配集。图G的含顶点最少的支配集称为最小支配集。最小支配集的顶点个数称为G的支配数, 记为y(G)或y。 例如,在下图中,D={0},D1={v1,v4,V7},D2={1,"3,V5,v6}都是G的支配集 前两个是极小支配集,D是最小支配集。y(G)=1 注:(1)最小支配集必是一个极小支配集,反之不然。 (2)任一支配集必含有一个极小支配集 (3)极小支配集不唯一,最小支配集一般也不唯一。 (4)对二部图G=(X,),X和Y都是支配集。 (5)若图G有完美匹配M,则从M中每边取一个端点构成的顶点集是一个支配集。 定理511设图G中无孤立顶点,则存在支配集D,使得D=(G)-D也是一个支配集 证明:无妨设G是连通图。于是G有生成树T。任取vo∈V(G D={v|v∈(G)且d(vo,v)=偶数} 则D=V(G)-D={|v∈v(G)且d(v,v)=奇数},且D和D都是支配集。证毕。 定理51,2设图G无孤立顶点,D1是一个极小支配集,则D1=(G)-D也是一个支配集。 证明(反证法):若不然,存在v∈D1,它与D中所有顶点都无边相连,但它又不是孤立顶 点,故必与D中顶点连边,因此D1-v0仍是支配集。这与D1是极小支配集矛盾。证毕 推论511设图G中无孤立顶点。对G的任一个极小支配集D1,必存在另一个极小支配集D2 使得D1∩D2=p 证明:由定理512,D1=V(G)-D1也是一个支配集,且D1∩D=φ。D中必含有一个极 小支配集D2。显然D1∩D2=φ。证毕
1 第五章 支配集、独立集、覆盖集和 Ramsey 数 本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的 图均为简单图。 §5.1 支配集、点独立集、点覆盖集 一、支配集(Domination set) 定义 5.1.1 设 D ⊆ V (G)，若对∀u ∈V (G) ，要么u ∈ D ，要么 u 与 D 中的某些顶点相邻， 则称 D 为图 G 的一个支配集。如果一个支配集的任何真子集都不是支配集，则称它为极小支 配集。图 G 的含顶点最少的支配集称为最小支配集。最小支配集的顶点个数称为 G 的支配数， 记为γ ( ) G 或γ 。 例如，在下图中， { } 0 0 D = v ， { , , } 1 1 4 7 D = v v v ， { , , , } 2 1 3 5 6 D = v v v v 都是 G 的支配集， 前两个是极小支配集， D0 是最小支配集。γ (G) = 1。 G 注：（1）最小支配集必是一个极小支配集，反之不然。 （2）任一支配集必含有一个极小支配集。 （3）极小支配集不唯一，最小支配集一般也不唯一。 （4）对二部图G = (X ,Y ) ，X 和 Y 都是支配集。 （5）若图 G 有完美匹配 M* ，则从 M* 中每边取一个端点构成的顶点集是一个支配集。 定理 5.1.1 设图 G 中无孤立顶点，则存在支配集 D，使得 D VG D = ( ) − 也是一个支配集。 证明：无妨设 G 是连通图。于是 G 有生成树 T。任取 ( ) v0 ∈V G 。令 D = {v | v ∈V(G) 且 ( , ) 0 d v v T ＝偶数}， 则 D VG D v v VG = −= ∈ ( ) {| ( ) 且 ( , ) 0 d v v T ＝奇数}，且 D 和 D 都是支配集。证毕。 定理 5.1.2 设图 G 无孤立顶点， D1是一个极小支配集，则 1 1 D VG D = ( ) − 也是一个支配集。 证明（反证法）：若不然，存在 0 D1 v ∈ ，它与 D1中所有顶点都无边相连，但它又不是孤立顶 点，故必与 D1中顶点连边，因此 1 0 D − v 仍是支配集。这与 D1是极小支配集矛盾。证毕。 推论 5.1.1 设图 G 中无孤立顶点。对 G 的任一个极小支配集 D1，必存在另一个极小支配集 D2 ， 使得 D1 ∩ D2 = φ 。 证明：由定理 5.1.2， 1 1 D VG D = − ( ) 也是一个支配集，且 D1 ∩ D = φ 。D1中必含有一个极 小支配集 D2 。显然 D1 ∩ D2 = φ 。证毕。 v7 v8 v1 v2 v6 v5 v3 v4 v0
定理513图G的支配集D是一个极小支配集当且仅当D中每个顶点ν满足下列条件之一: (1)存在∈V(G)-D使得N(u)∩D={v}:(2)N(v)∩D=φ。 证明:充分性:设D是G的一个支配集。对D中任一个顶点v,因γ满足上述条件之一,故 要么与ν相邻的某个顶点不能被D-{v}支配,要么v自己不能被D-{v}支配,可见,D-{v} 不再是支配集。这表明D是极小支配集。 必要性:设D是G的一个极小支配集,则对D中任一个顶点v,D-{}不再是支配集。因 此在D-{v}之外存在顶点u,它不与D-{v}中任何点相邻。如果u=v,则说明v不与D 中任何点相邻,即N(v)∩D=φ:如果u≠v,则因D是支配集,故u必与v相邻,但不与 D中其它点相邻,即N(a)∩D={v}。证毕 定理514设G是无孤立顶点的图,则G必有最小支配集D满足:对v∈D,丑∈G-D 使得N(u)∩D={v} 证明:用反证法。在G的全部最小支配集中,设D为使得导出子图G[D]含边数最多的一个。 假定定理结论不真,即 v∈D,使得对vu∈G-D都有N(u)∩D≠{v}。 由定理5.13,N(v)∩D=φ,即D中所有其它点都不与v相邻。而上式表明,G-D中每 个点要么不与v相邻,要么既与v相邻也与D中另外某些点相邻。因G无孤立点,故v在G-D 中必有某个邻点w,令D1=(D-{v)U{w},则D也是G的一个最小支配集,但其导出子 图G[D]含的边数比G[D中多。这与D的取法矛盾。证毕。 以下是关于支配数的几个估计式。 定理515如果图G无孤立顶点,则(G)≤ 证明:设D是G的一个极小支配集,则由定理512,V(G)-D也是G的支配集。因此, y(G)≤minDⅤ(G)-D}≤2 证毕 定理51.6( Arnautov197, Payan1975)设G是一个最小度为d图,则()shn(GAN 1+δ 证明:对G的任一非空顶点子集S∈V(G),用U表示未被S中顶点支配的所有顶点之集。 对v∈(G),用N'(v)表示顶点v及其所有邻点组成的集合,即N(v)=N(v)∪{v}。由 于U中每个顶点至少有k个邻点,故∑|N()|2Ul(6+1)。从而在(G)-S中至少有 个顶点x,它在求和过程中至少被重复计算|(6+1) 次。(否则,若V(G)-S中每个点被 重复计算都少于C|(+1) 次,则∑|N()<(U-|sD(6+1)<U(+1),与前 式矛盾),这意味着在(G)-S中存在某个顶点x,它支配U中至少1(1+1D各顶点
2 定理 5.1.3 图 G 的支配集 D 是一个极小支配集当且仅当 D 中每个顶点 v 满足下列条件之一： （1）存在u VG D ∈ − ( ) 使得 Nu D v ( ) {} ∩ = ；（2） Nv D ( ) ∩ = φ 。 证明：充分性：设 D 是 G 的一个支配集。对 D 中任一个顶点 v，因 v 满足上述条件之一，故 要么与 v 相邻的某个顶点不能被 D v −{ }支配，要么 v 自己不能被 D v −{ }支配，可见，D v −{ } 不再是支配集。这表明 D 是极小支配集。 必要性：设 D 是 G 的一个极小支配集，则对 D 中任一个顶点 v， D v −{ }不再是支配集。因 此在 D v −{ }之外存在顶点 u，它不与 D v −{ }中任何点相邻。如果u v = ，则说明 v 不与 D 中任何点相邻，即 Nv D ( ) ∩ = φ ；如果u v ≠ ，则因 D 是支配集，故 u 必与 v 相邻，但不与 D 中其它点相邻，即 Nu D v ( ) {} ∩ = 。证毕。 定理 5.1.4 设 G 是无孤立顶点的图，则 G 必有最小支配集 D 满足：对∀v D ∈ ，∃∈ − uGD 使得 Nu D v ( ) {} ∩ = 。 证明：用反证法。在 G 的全部最小支配集中，设 D 为使得导出子图 G[D]含边数最多的一个。 假定定理结论不真，即 ∃v D ∈ ，使得对∀uGD ∈ − 都有 Nu D v ( ) {} ∩ ≠ 。 由定理 5.1.3， Nv D ( ) ∩ = φ ，即 D 中所有其它点都不与 v 相邻。而上式表明，G D− 中每 个点要么不与 v 相邻，要么既与 v 相邻也与 D 中另外某些点相邻。因 G 无孤立点，故 v 在G D− 中必有某个邻点 w，令 1 D Dv w = − ( { }) { } ∪ ，则 D1也是 G 的一个最小支配集，但其导出子 图 G[D1]含的边数比 G[D]中多。这与 D 的取法矛盾。证毕。 以下是关于支配数的几个估计式。 定理 5.1.5 如果图 G 无孤立顶点，则 (G) 2 υ γ ≤ 。 证明：设 D 是 G 的一个极小支配集，则由定理 5.1.2， V(G) D− 也是 G 的支配集。因此， (G) min{| D |, | V(G) D |} 2 υ γ ≤ −≤ 。 证毕。 定理 5.1.6 (Arnautov 1974, Payan 1975) 设 G 是一个最小度为δ 图，则 1 ln( 1) (G) 1 δ γ υ δ + + ≤ + 。 证明：对 G 的任一非空顶点子集S V(G) ⊆ ，用 U 表示未被 S 中顶点支配的所有顶点之集。 对∀ ∈v VG( ) ，用 N v( ) ∗ 表示顶点 v 及其所有邻点组成的集合，即 N v Nv v ( ) ( ) {} ∗ = ∪ 。由 于 U 中每个顶点至少有 k 个邻点，故 | ( ) | | | ( 1) v U Nv U δ ∗ ∈ ∑ ≥ + 。从而在VG S ( ) − 中至少有一 个顶点 x，它在求和过程中至少被重复计算 | | ( 1) U δ υ + 次。(否则，若VG S ( ) − 中每个点被 重复计算都少于 | | ( 1) U δ υ + 次，则 | | | ( ) | ( | S |) ( 1) | | ( 1) v U U Nv U υ δδ υ ∗ ∈ ∑ < − ⋅ +< + ，与前 式矛盾)。这意味着在VG S ( ) − 中存在某个顶点 x，它支配 U 中至少 | | ( 1) U δ υ + 各顶点
现在我们通过迭代来生成G的一个支配集,用S表示在迭代过程中形成的支配集的一部 分,初始时可取最大度顶点放入S。在迭代的每一步选择一个顶点放入S,所选择的顶点应能 够尽可能多地支配当前的S尚未支配的顶点。由前一部分的结论,如果当前的S尚未支配的 顶点有U=k个,则在(G)-S中存在某个顶点x,它支配U中至少k(6+1) 个顶点。因 此按照我们的选点规则,再选择一个点放入S后,剩下未被支配的顶点不超过M、+1个 n(δ+1 在+1步后,未被支配的顶点个数至多为 +1) (1 6+1 (上式推导中用到不等式1-P<e)。将当前S中的点和未被S支配的点放在一起,便组成 G的一个支配集,它含有+1)+D=1+1mo+1),个顶点。结论得证。 定理517对任何图G,有 2x4G|s(G)sD-△(G) 证明:设D是G的一个最小支配集,则v(G)-Ds∪N(v),因此(G)-D≤△(G)。 而|V(G)-D=b-|D|,|D=y(G),故U-y(G)≤y(G)△(G),于是y(G)≥ 1+△(G) 图的支配集是内容相当丰富的一个研究专题,它在许多学科领域有重要的应用,是目前研 究的一个热点方向[1~5]。进一步的了解可参看 Haynes- Hedetniemi- Slater的长达1200页的 专著6]。支配集理论在电力网络中的应用见文献[]。支配集在无线通信网络中的应用见文献 [8~l1]l [1B.G. Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics, 154(2006) 1541-1546 [2]TW. Haynes, M.A. Henning, and J. Howard, Locating and total dominating sets in trees, Discrete Applied Mathematics, 154(2006), 1293-1300 3] J.S. Deogun, and D. Kratsch, Dominating pair graphs, SIAM J. Discrete Mathematics 15:3(2001-2002),353-366 [4] Chin Lung Lu, Ming-Tat Ko and Chuan Yi Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Mathematics, 119(2002), 227-250 [5]Chin Lung Lu and Chuan Yi Tang, Weighted efficient domination problem on some perfect graphs, Discrete Applied Mathematics, 117(2002), 163-182 [].W. Haynes, S.T. Hedetniemi, and P J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker. Inc. 1998 [7 T.W. Haynes, S M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Mathematics, 15: 4(2001-2002), 519-529
3 现在我们通过迭代来生成 G 的一个支配集，用 S 表示在迭代过程中形成的支配集的一部 分，初始时可取最大度顶点放入 S。在迭代的每一步选择一个顶点放入 S，所选择的顶点应能 够尽可能多地支配当前的 S 尚未支配的顶点。由前一部分的结论，如果当前的 S 尚未支配的 顶点有| | U k = 个， 则在VG S ( ) − 中存在某个顶点 x，它支配 U 中至少 k( 1) δ υ + 个顶点。因 此按照我们的选点规则，再选择一个点放入 S 后，剩下未被支配的顶点不超过 1 k(1 ) δ υ + − 个。 在 ln( 1) 1 δ υ δ + + 步后，未被支配的顶点个数至多为 ln( 1) 1 1 ln( 1) (1 ) 1 e δ υ δ δ δ υ υ υ υ δ + ⋅ + + − + − <= + 。 （上式推导中用到不等式1 p p e− − < ）。将当前 S 中的点和未被 S 支配的点放在一起，便组成 G 的一个支配集，它含有 ln( 1) 1 δ υ δ + + + 1 υ δ + = 1 ln( 1) 1 δ υ δ + + + 个顶点。结论得证。 定理 5.1.7 对任何图 G，有 (G) (G) 1 (G) υ γ υ ⎡ ⎤ ≤ ≤ −Δ ⎢ ⎥ ⎢ ⎥ + Δ 。 证明：设 D 是 G 的一个最小支配集，则 V(G) D ( ) v D N v ∈ − ⊆ ∪ ，因此|V(G) D| |D| (G) − ≤ ⋅Δ 。 而| V(G) D | | D | − =−υ ，| D | (G) = γ ，故υ − γ γ (G) (G) (G) ≤ Δ ，于是 (G) 1 (G) υ γ ⎡ ⎤ ≥ ⎢ ⎥ ⎢ ⎥ + Δ 。 证毕。 图的支配集是内容相当丰富的一个研究专题，它在许多学科领域有重要的应用，是目前研 究的一个热点方向[1~5]。进一步的了解可参看 Haynes－Hedetniemi－Slater 的长达 1200 页的 专著[6]。支配集理论在电力网络中的应用见文献[7]。支配集在无线通信网络中的应用见文献 [ 8~11]。 [1] B.G.. Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics, 154(2006), 1541-1546. [2] T.W. Haynes, M.A. Henning, and J. Howard, Locating and total dominating sets in trees, Discrete Applied Mathematics, 154(2006), 1293-1300. [3] J.S. Deogun, and D. Kratsch, Dominating pair graphs, SIAM J. Discrete Mathematics, 15:3(2001-2002), 353-366. [4] Chin Lung Lu, Ming-Tat Ko and Chuan Yi Tang, Perfect edge domination and efficient edge domination in graphs, Discrete Applied Mathematics, 119(2002), 227-250. [5] Chin Lung Lu and Chuan Yi Tang, Weighted efficient domination problem on some perfect graphs, Discrete Applied Mathematics, 117(2002), 163-182. [6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., 1998. [7] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Mathematics, 15:4(2001-2002), 519-529
[8]I. Stojmenovic, M. Seddigh, and J. Zunic, Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks, Proc. IEEE Hawaii Int. Conf. On System Sciences an.2001 [9]. Wu, and H.L. Li, On calculating connected dominating set for efficient routing in ad wireless networks, Proceedings of the 3 ACM International Workshop on Discrete Algorithms Methods for Mobile Computing and Communications, 1999,7-14 [10 S. Guha, and S. Khuller, Approximation algorithms for connected dominating sets Algorithmica,20:4(1998),347-387 [11]B Das, and V Bharghavan, Routing in ad hoc networks using minimum connected dominating sets, ICC97, Montreal, Canada, June, 1997 、点独立集( vertex independent se) 定义5.1.2设Ⅰ∈V(G),若l中任二顶点均不相邻,则称l为图G的一个点独立集(简称 独立集);若对vu∈V(G)\,U{都不再是G的独立集,则称独立集为图G的一个 极大点独立集。G的含点数最多的点独立集称为最大点独立集,它含点的个数称为G的独立 数,记为a(G)或a 例如,在下图中,D={V},1=智1,v4,"n},l2={1,v3,V5,"}都是G的独立集, 且都是极大独立集,其中l2是最大独立集,a(G)=4。 些文献中将独立集称为稳定集( stable set),相应地将独立数称为稳定数。 独立集与支配集的关系 定理518图G的极大独立集必是G的极小支配集。 证明:设I是G的一个极大独立集。对wu∈I(G)\I,u必与/中某顶点相邻(否则与极大 性矛盾)。可见/是一个支配集。又对回v∈I,v必与I\{v}中的顶点不相邻,可见/是极小 支配集。证毕。 注:该定理的逆不真。例如在下图中,{v1,v2}是极小支配集,但却不是极大独立集。实际上 它根本不是独立集
4 [8] I. Stojmenovic, M. Seddigh, and J. Zunic, Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks, Proc. IEEE Hawaii Int. Conf. On System Sciences, Jan. 2001. [9] J. Wu, and H.L.Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 1999,7-14. [10] S. Guha, and S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica, 20:4(1998), 347-387. [11] B. Das, and V. Bharghavan, Routing in ad hoc networks using minimum connected dominating sets, ICC’97, Montreal, Canada, June, 1997. 二、点独立集(vertex independent set) 定义 5.1.2 设 I ⊆ V（G），若 I 中任二顶点均不相邻，则称 I 为图 G 的一个点独立集（简称 独立集）；若对∀u ∈V(G) \ I ， I ∪{u}都不再是 G 的独立集，则称独立集 I 为图 G 的一个 极大点独立集。G 的含点数最多的点独立集称为最大点独立集，它含点的个数称为 G 的独立 数，记为α(G) 或α 。 例如，在下图中， { } 0 0 I = v ， { , , } 1 1 4 7 I = v v v ， { , , , } 2 1 3 5 7 I = v v v v 都是 G 的独立集， 且都是极大独立集，其中 2 I 是最大独立集，α(G) = 4 。 一些文献中将独立集称为稳定集(stable set)，相应地将独立数称为稳定数。 z 独立集与支配集的关系 定理 5.1.8 图 G 的极大独立集必是 G 的极小支配集。 证明：设 I 是 G 的一个极大独立集。对∀u ∈V(G) \ I ，u 必与 I 中某顶点相邻（否则与极大 性矛盾）。可见 I 是一个支配集。又对∀v ∈ I ，v 必与 I \ {v}中的顶点不相邻，可见 I 是极小 支配集。证毕。 注：该定理的逆不真。例如在下图中，{ , } 1 2 v v 是极小支配集，但却不是极大独立集。实际上 它根本不是独立集。 v1 v2 v4 v3 v7 v8 v1 v2 v6 v5 v3 v4 v0 G
但我们有如下结论 定理519若I是独立集,则它是极大独立集当且仅当它是支配集 证明:必要性由定理518显然。 充分性:设l是独立集又是支配集,则对vv∈(G)\1,因/是支配集,v必与I中某顶点相 邻。故U{v}不是独立集。可见/是极大独立集。 注:(1)由定理518和定理5.1.9,虽然G的一个独立集未必是G的支配集,但一个极大独 立集必是G的极小支配集;反过来,G的一个支配集要么不是独立集,要么是极大独立集; (2)一个支配集若不是极小支配集,则必不是G的独立集。 定理5110对任何图G,a(G)≥y(G)。 证明:设I是G的一个最大独立集,则它必是一个极大独立集,由定理5.1.8,I是G的一个 (极小)支配集,因此y(G)SIF=a(G)。证毕。 注:定理51.10中的等号未必总成立,也就是说,虽然G的一个最大独立集必是G的极小支 配集,但它未必是最小支配集。例如完全二部图K13,最大独立集含三个点,而最小支配集含 一个点。 点独立集与连通度 定理5111( Bondy,1978)设vG)≥2。若图G中任二不相邻顶点x与y均有 d(x)+d(y)≥v(G),则a(G)≤k(G)。 证明:首先易知G是连通的(若G不连通,设x、y属于不同的连通分支G1,G,,则 d(x)SG1|-1,d(y)≤G2|-1,从而d(x)+d(y)G1|+|G2|-2<v)。 若G为完全图K,则a(K,)=1≤v-1=K(K,),结论成立。下设G不是完全图。用 反证法证明结论。 假定a(G)≥k(G)+1。设和S分别是G中的最大点独立集和最小点割集。则 Fa(G)≥2,|SF=K(G)=k。设G\S的连通分支为G1,G2,…G1,(≥2)。由于对 vx,y∈I,|N(x)∪NG(y)kv-a。 (含a个顶点) GI含v-a个顶点) kh ING(x)nNG()=ING(x)I+ING(y)I-ING(x)UNG() =d(x)+d(y)-|Nc(x)UNa(y)|≥v-(-a)=a≥k+1 这表明Ⅰ\S含在G\S的同一个连通分支中(因在I\S中任二点x与y有公共的邻点,故有
5 但我们有如下结论。 定理 5.1.9 若 I 是独立集，则它是极大独立集当且仅当它是支配集。 证明：必要性由定理 5.1.8 显然。 充分性：设 I 是独立集又是支配集，则对∀v ∈V(G) \ I ，因 I 是支配集，v 必与 I 中某顶点相 邻。故 I ∪{v}不是独立集。可见 I 是极大独立集。 注：（1）由定理 5.1.8 和定理 5.1.9，虽然 G 的一个独立集未必是 G 的支配集，但一个极大独 立集必是 G 的极小支配集；反过来，G 的一个支配集要么不是独立集，要么是极大独立集； （2）一个支配集若不是极小支配集，则必不是 G 的独立集。 定理 5.1.10 对任何图 G，α(G) (G) ≥ γ 。 证明：设 I 是 G 的一个最大独立集，则它必是一个极大独立集，由定理 5.1.8，I 是 G 的一个 （极小）支配集，因此γ (G) | I | (G) ≤ = α 。证毕。 注：定理 5.1.10 中的等号未必总成立，也就是说，虽然 G 的一个最大独立集必是 G 的极小支 配集，但它未必是最小支配集。例如完全二部图 K1,3，最大独立集含三个点，而最小支配集含 一个点。 z 点独立集与连通度 定 理 5.1.11 (Bondy, 1978) 设 ν (G) ≥ 2 。若图 G 中任二不相邻顶点 x 与 y 均 有 d (x) d ( y) (G) G + G ≥ν ，则α(G) ≤ κ (G) 。 证明：首先易知 G 是连通的（若 G 不连通，设 x、y 属于不同的连通分支 1 2 G , G ，则 dG (x) ≤| G1 | −1， dG ( y) ≤| G2 | −1，从而dG (x) + dG ( y) ≤| G1 | + | G2 | −2 <ν ）。 若 G 为完全图 Kν ，则 ( ) 1 1 ( ) α Kν = ≤ν − = κ Kν ，结论成立。下设 G 不是完全图。用 反证法证明结论。 假定α(G) ≥ κ (G) +1 。设 I 和 S 分别是 G 中的最大点独立集和最小点割集。则 | I |= α(G) ≥ 2 ，| S |= κ (G) = k 。设G \ S 的连通分支为G G "Gl , , 1 2 ， (l ≥ 2) 。由于对 ∀x, y ∈ I ，| NG (x) ∪ NG ( y) |≤ν −α 。 故 | N (x) N ( y) | G ∩ G ＝| N (x) | | N ( y) | G + G | N (x) N ( y) | − G ∪ G ＝ d (x) d ( y) G + G | N (x) N ( y) | − G ∪ G ≥ν − (ν −α) = α ≥ k +1。 这表明 I \ S 含在G \ S 的同一个连通分支中（因在 I \ S 中任二点 x 与 y 有公共的邻点，故有 I (含α 个顶点) y x G-I (含ν −α 个顶点)