完全二部图$K_{n,n}$中必存在单色4-环的最小$n$值求解

嘿，我来帮你搞定这个竞赛题，这题本质是拉姆塞理论在二部图里的应用，咱们一步步拆解清楚：

首先明确问题：给完全二部图$K_{n,n}$的所有边染红、蓝两种颜色，求最小的$n$，使得不管怎么染，都一定能找到一个单色的4-环（也就是四个顶点构成的环，四条边全是同一种颜色）。

第一步：先看$n=5$时，存在没有单色4-环的染色方式 #

这说明$n=5$不满足“任意染色都有单色4-环”的要求，咱们可以构造出这样的染色：

• 把二部图的两个顶点集分别记为$A={a_1,a_2,a_3,a_4,a_5}$和$B={b_1,b_2,b_3,b_4,b_5}$
• 给$A$中每个顶点的红边对应$B$里的两个顶点，规则是：$a_i$红连$b_i$和$b_{i+1}$（下标模5，比如$a_5$红连$b_5$和$b_1$）
• 剩下的边全染蓝色

你可以验证一下：

• 红边里，任意两个$A$中的顶点最多只有1个共同的红色邻居，没法形成4-环（4-环需要两个顶点有至少2个同色共同邻居）
• 蓝边里，任意两个$A$中的顶点也最多只有1个共同的蓝色邻居，同样不会出现4-环

所以$n=5$的时候，存在“无单色4-环”的染色，不符合题目的要求。

第二步：证明$n=6$时，任何染色都必有单色4-环 #

咱们用鸽巢原理来推导，逻辑很清晰：

1. 先取$A$中的任意一个顶点$a_1$，它连向$B$的6条边里，根据鸽巢原理，至少有3条是同一种颜色，假设是红色（蓝色的情况完全对称），记这3条红边连的$B$中顶点为$b_1,b_2,b_3$。
2. 现在看$b_1,b_2,b_3$这三个顶点，它们连向$A$中剩下的5个顶点（$a_2$到$a_6$）的边：
   • 如果$A$中存在某个顶点$a_i$（$i≥2$），它和$b_1,b_2,b_3$中的至少两个连的是红边，那$a_1,a_i$加上这两个$B$顶点就直接构成了红色4-环，问题解决。
   • 如果$A$中每个$a_i$（$i≥2$）和$b_1,b_2,b_3$连的红边都不超过1条，那每个$a_i$和这三个顶点连的蓝边至少有2条。
3. 接下来看这5个$a_i$的蓝边：每个$a_i$对应$b_1,b_2,b_3$中的一个2-顶点子集（就是它蓝连的那两个$B$顶点）。而$b_1,b_2,b_3$的2-子集总共只有3种：${b_1,b_2},{b_1,b_3},{b_2,b_3}$。
4. 5个$a_i$对应3种子集，根据鸽巢原理，至少有2个$a_i$对应同一个2-子集。比如$a_2$和$a_3$都蓝连$b_1$和$b_2$，那$a_2-b_1-a_3-b_2-a_2$就是一个蓝色4-环，完美。

不管哪种情况，$n=6$时都逃不掉单色4-环的存在。

结论 #

所以满足条件的最小$n$就是6。

备注：内容来源于stack exchange，提问作者Nishkarsh