Question

【题目】设、为平面上两个点集，满足，，且任意三点不共线.在集合和间各连若干条线段，每条线段均一个端点在集合中，另一个端点在集合中，且任意两点间至多连一条线段，记所有线段构成的集合为.若集合满足对于集合或中任意一点均至少连出条线段，则称集合是“一好的”.试确定的最大值，使得去掉任意一条线段，集合均不是一好的.

Answer 1

【答案】见解析

【解析】

设集合中有个点引出边数不为条，有个点恰引出条边，设集合中有个点引出边数不为条，有个点恰引出条边.

由于对称性，不妨设.

记，其中，为集合中所有恰引出条线段的点构成的集合，为集合中除去外余下的点构成的集合，记B=，其中，为集合中所有恰引出条线段的点构成的集合，为集合中除去外余下的点构成的集合.

则满足以下两个估计：

（1） .

注意到，集合中的点仅能与集合中的点相邻，故对于，

.

（2）.

对于集合中的任意一条边，至少有一个端点在集合或内，因此，

.

由（1）、（2）知

.

若，则；

若，则.

故当时，

；

当时，，即

构造：（i）若，构造两个完全的二部图，即将集合中的点划分为两个集合、；将集合中的点划分为两个集合、，，其中，将集合中每一点与集合中每一点均连线，将集合中每一点和集合中每一点均连线.

（ii）若，对集合、进行如下的划分：

，

，；

，

，.

此时，将集合中的每一点与集合中的每一点相连，将集合中的每一点与集合i中的每一点均相连.然后，在和这两个点集间再构造一个的二部正则图即可.