王晓丽

（晋中学院数学系，山西晋中 030619）

1 预备知识

定义1d-（ν），d+（ν）是顶点ν 的入度和出度，定义d（ν）＝min｛d-（ν），d+（ν）｝为顶点ν 的度.

定义2δ-，δ+表示D 的最小入度和最小出度，定义δ＝min｛δ-，δ+｝为有向图D 的最小度.

定义3有向图D 的顶点个数定义为D 的阶，记作n（D）＝n，有向图D 的弧的条数记作m（D）＝m.

定义4把顶点度的不增序列d1≥d2≥L≥dn定义为有向图D 的度序列.

定义5如果有向图D 的基础图UG（D）不含r+1 个顶点的完全子图，称有向图D 的团数ω（D）≤r.

定义6无2-圈且无环的有向图称为定向图.

定义7弧连通度λ 与最小度δ 显然满足λ≤δ，当λ＝δ 时，称有向图D 是极大弧连通的.

引理1［1］f（x）是［L，R］上的连续凸函数，若l，r∈［L，R］，满足l+r ＝L+R，有

文中使用但未定义的记号、术语请参见文献［3］.

2 主要结论

证明若UG（D［S］）不含r 个顶点的团，则

若UG（D［S］）包含r 个顶点的团，取顶点集Q∈S，UG（Q）是不包含r 个顶点的团的顶点数最多的顶点集，设D 的每个顶点的邻集的导出子图不包含r 个顶点的团.如果D 的顶点ν1的邻集的导出子图包含r 个顶点的团，则UG（D）包含r＋1 个顶点的团，与定向图D 的团数ω（D）≤r 矛盾！

因此

由S、T 的选取知S∪T 包含D 的k 个最高度顶点，所以