由于图 G 不含扇 F3 为子图，故 Gv1 , v2 , v3 , v4 , v5 , v6 不含 3k2  ,以下证明

eGv1 , v2 , v3 , v4 , v5 , v6   11 . (1)当 d vi   5 i  1,2,3,4,5,6时，由 Euler 定理知

2e(G) d (v) 6 5 6 36 ,来.自>优:尔论`文/网www.chuibin.com

vV G 

故有

ex7; F3 18 .

而当 ex7; F3 18 ,则有 d vi 5 i 1,2,3,4,5,6,此时必有图 G 含扇 F3 ,故对于 7 阶图 G 中不含扇 F3 必有 ex7; F3 17 .

(2)当存在1 i 6 使 d vi 6 时，不妨设 d v1 6 , v1 v0 , v2 , v3 , v4 , v5 , v6 ,即如 下图所示：

若得到不含扇 F3 的 7 阶图且有最大边数，则从 v2 引边连接 v3 、 v4 、 v5 和 v6 ，故 有 d v2 6 ,且在 v3 、 v4 、 v5 、 v6 中不能产生新的边，故有

eGv1, v2 , v3 , v4 , v5 , v6   9  11 ,

于是

eG  d v0  eGv1 , v2 , v3 , v4 , v5 , v6   6  9  15  17 .

综合（a）、（b）可知， eG17 . 由此，