Colorea los bordes de $K_6$ rojo o azul. Demuestra que existe un ciclo de longitud 4 con aristas monocromáticas.

Question

Colorea los bordes de $K_6$ rojo o azul. Demuestra que existe un ciclo de longitud 4 con aristas monocromáticas.

Intento: Sé que tengo que...

demuestra que debe haber DOS vértices con "grado rojo" al menos 3, o dos con "grado azul" al menos 3. Llámalos U y V. (Supondremos que estamos en el caso rojo; el caso azul es similar.) Ahora, pregunta si están conectados por una arista roja, y cuántos vecinos adyacentes rojos comparten. Si analizas esto, sólo debería haber unos pocos casos que considerar, y cada uno debería ser relativamente sencillo. Para cada caso, demostrarás que ese caso no puede darse en $K_6$ o que da lugar a un 4-ciclo monocromático.

Answer 1

Yo haré la mayor parte, dejando algunos detalles para que los compruebes. Es muy útil hacer diagramas para los distintos casos.

Dado que cada vértice de $K_6$ tiene grado $5$ cada vértice debe tener al menos $3$ bordes del mismo color. Llamamos rojo a un vértice si tiene al menos $3$ bordes rojos y azul si tiene al menos $3$ bordes azules. Dado que hay $6$ vértices en total, debe haber al menos $3$ vértices del mismo color; supongamos que hay al menos $3$ vértices rojos, digamos $u,v$ y $w$ . Hay varios casos.

Supongamos primero que las tres aristas $uv,vw$ y $uw$ son azules. Deja que los otros $3$ los vértices sean $x,y$ y $z$ . Los vértices $u,v$ y $w$ son rojos, por lo que cada arista de uno de $u,v$ y $w$ a $x,y$ o $z$ debe ser rojo, y $u,x,v,y,u$ es un rojo $4$ -ciclo.

Así, podemos suponer que dos de estos vértices rojos, digamos $u$ y $v$ están conectados por un borde rojo. Cada una de ellas está conectada por aristas rojas con (al menos) $2$ otros vértices. Digamos que $u$ está conectada por aristas rojas a $u_1$ y $u_2$ y $v$ está conectada por aristas rojas a $v_1$ y $v_2$ .

• Si $\{u_1,u_2\}=\{v_1,v_2\}$ podemos suponer que $u_1=v_1$ y $u_2=v_2$ . En este caso $u,u_1,v,u_2,u$ es un rojo $4$ -ciclo.
• Si $\{u_1,u_2\}\cap\{v_1,v_2\}=\varnothing$ entonces el $6$ vértices $u,v,u_1,u_2,v_1,v_2$ son distintos, y uno de ellos, digamos $u_1$ , debe ser $w$ . Hay al menos $3$ bordes rojos en $w$ uno de los cuales es $uw$ . Si $wv_1$ es una arista, entonces $u,w,v_1,v,u$ es un rojo $4$ -y, de forma similar, si $wv_2$ es un borde rojo. Si ninguno de los dos $wv_1$ ni $wv_2$ es un borde rojo, entonces $wu_2$ y $wv$ deben ser ambos rojos, y $u,v,w,u_2,u$ es un rojo $4$ -ciclo.

La posibilidad restante es que los conjuntos $\{u_1,u_2\}$ y $\{v_1,v_2\}$ tienen exactamente un elemento en común; digamos $u_1=v_1$ . Te dejo que compruebes que si alguno de los bordes $u_1u_2,u_1v_2,u_2v_2,uv_2$ o $vu_2$ es rojo, entonces hay un rojo $4$ -por lo que podemos suponer que todas estas aristas son azules. Esto significa que $u_2$ y $v_2$ son vértices azules, por lo que $w=u_1$ o $w$ es el sexto vértice, diferente de todos los $u,v,u_1,u_2$ y $v_2$ .

• Si $w=u_1$ , dejemos que $x$ sea el sexto vértice; la arista $wx$ debe ser rojo, ya que $w$ es un vértice rojo, y $wu_2$ y $wv_2$ son azules. Si alguno de los bordes de $x$ a $u,v,u_2$ o $v_2$ es rojo, es fácil encontrar un $4$ -ciclo, por lo que se supone que todos son azules; entonces $x,u_2,v_2,u,x$ es un azul $4$ -ciclo.

• Si $w$ es el sexto vértice, tiene aristas rojas hacia al menos $3$ de los vértices $u,v,u_1,u_2$ y $v_2$ . En particular, debe tener una arista roja hacia al menos uno de los vértices $u_1,u_2$ y $v_2$ . Supongamos que $wu_1$ es de color rojo; se puede comprobar que no importa cuál de los bordes $wu,wv,wu_2$ o $wv_2$ es rojo, hay un rojo $4$ -ciclo. (Por ejemplo, si $wu$ es rojo, podemos utilizar $w,u,v,u_1,w$ y si $wu_2$ es rojo, podemos utilizar $w,u_2,u,u_1,w$ .) Así, podemos suponer que $wu_1$ es azul y $wu_2$ digamos, es rojo. Pero entonces $wv$ es rojo, y tenemos un $4$ -ciclo $w,u_2,u,v,w$ o $wv$ es azul, y tenemos un $4$ -ciclo $w,u_1,u_2,v,w$ .

Answer 2

Fija un vértice y llama a sus vecinos rojos o azules en función de las aristas que llevan a ellos. Si hay $k$ vecinos rojos, el $5-k$ los vecinos azules tienen como máximo $\binom{5-k}2$ bordes rojos entre sí. Si un vecino azul tiene más de una arista roja con un vecino rojo, podemos formar un $4$ -ciclo; si no, es como máximo $5-k$ más bordes rojos. Si dos aristas rojas entre los vecinos rojos comparten un punto final, podemos formar un $4$ -ciclo; si no, es como máximo $\left\lfloor\frac k2\right\rfloor$ más bordes rojos, para un total de $k+\binom{5-k}2+5-k+\left\lfloor\frac k2\right\rfloor$ $=5+\binom{5-k}2+\left\lfloor\frac k2\right\rfloor$ . Esto es $7$ para $k\ge3$ y tenemos $15$ aristas, lo que lleva a la contradicción de que el color de la arista mayoritaria es minoritario en cada vértice.

Answer 3

No estoy seguro de que estés tratando de demostrar lo correcto, porque no necesariamente hay un ciclo monocromático de longitud 4 (ver la imagen). En realidad, el número de Ramsey R(3,3)=6, lo que significa que siempre podemos encontrar un ciclo monocromático de longitud 3.

Puedes consultar este enlace si quieres ver la prueba monocromática de 3 ciclos.

https://plus.maths.org/content/friends-and-strangers