OK，我想了个更简单的证明
首先n个城市每个点的度至少是n-4，不然要么一个三角形没边要么有4个点全连
9个的话就是度至少是5，但是因为度的和是偶数所以一定有一个顶点度至少是6，考虑这个顶点练的6个点，根据ramsey定理有么有个三角形全连这样就有4个点全连要么有全不连的三角形，矛盾，所以9不行，8的话可以用我前面给的构造，这个应该可以推广到一般情况
【 在 lonelycat 的大作中提到: 】
: 感觉他就是反复用ramsey定理吧，不过这个题没啥意思了，因为一般广义的题这么做的了么，比如每四个点有一条线但是没有5个 ...
--
FROM 120.229.142.*