某个国家有 $n$ 个城市（$n\geqslant 3$），每两个城市之间都有一条双向航线。这个国家有两个航空公司，每条航线由一家公司经营。一个女数学家从某个城市出发，经过至少两个其他城市，回到出发地。如果无论怎样选择出发城市和路径，都无法只乘坐一家公司的航班，求 $n$ 的最大值。
【难度】
【出处】
2012第11届CGMO试题
【标注】
【答案】
4
【解析】
将每座城市看作一个顶点，每条航线看作一条边，每家航空公司对应一种颜色，则该国的航线网可以看成边被二染色的 $n$ 个顶点的完全图。
由条件知任意一个圈都包含两种颜色的边，即同一种颜色的边构成的子图没有圈。因此，每种颜色的边数都不超过 $n-1$ 。这表明总边数不超过 $2(n-1)$ 。
另一方面，$n$ 个顶点的完全图的边数为 $\frac{n(n-1)}{2}$，因此 $\frac{n(n-1)}{2}\leqslant 2(n-1)$，解得 $n\leqslant 4$ 。
当 $n=4$ 时，记四个城市分别为 $A$、$B$、$C$、$D$，若 $AB$、$BC$、$CD$ 这三条航线由第一家航空公司运营，$AC$、$AD$、$BD$ 这三条航线由第二家航空公司运营，则容易看出每家航空公司运营的航线均为一个链，不包含圈，即这样的情形满足条件。
综上，$n$ 的最大值为4．
由条件知任意一个圈都包含两种颜色的边，即同一种颜色的边构成的子图没有圈。因此，每种颜色的边数都不超过 $n-1$ 。这表明总边数不超过 $2(n-1)$ 。
另一方面，$n$ 个顶点的完全图的边数为 $\frac{n(n-1)}{2}$，因此 $\frac{n(n-1)}{2}\leqslant 2(n-1)$，解得 $n\leqslant 4$ 。
当 $n=4$ 时，记四个城市分别为 $A$、$B$、$C$、$D$，若 $AB$、$BC$、$CD$ 这三条航线由第一家航空公司运营，$AC$、$AD$、$BD$ 这三条航线由第二家航空公司运营，则容易看出每家航空公司运营的航线均为一个链，不包含圈，即这样的情形满足条件。
综上，$n$ 的最大值为4．
答案
解析
备注
