Borde para colorear un gráfico para encontrar un monocromático $K_{2,n}$

Question

Estoy tratando de probar o refutar la siguiente declaración: Vamos a $n>1$ ser un entero positivo. Entonces existe un gráfico de $G$ de tamaño 4n-1 tal que si los bordes de $G$ son de color rojo o azul, no importa en que forma, $G$ definitivamente contiene un monocromático $K_{2,n}$.

Traté de ver un par de casos en la esperanza de descubrir un contra-ejemplo. Para n=2 $G$ tiene que tener el tamaño de 7. El gráfico que sin duda es de la forma "Cuadrada + 3 aristas". Por otra parte, se debe tener la propiedad de que si entre el 7 bordes cualquier 3 se eliminan el resto de gráfico es un cuadrado. Yo podía construir cualquier gráfico. ¿Hay alguna justificación ¿por qué la gráfica no puede existir, negando así la declaración?

Answer 1

La afirmación no se sostiene por $n = 2$. Considere las siguientes observaciones para cualquier gráfico de $G$ esperando para satisfacer la demanda.

1. $G$ $K_{2,2}$ con tres bordes anexa.
2. Sin pérdida de generalidad, $G$ está conectado y no tiene hojas.
3. $G$ tiene al menos cinco vértices.

Dibujar un $K_{2,2}$ y más un vértice. Desde el vértice no está aislado y no es una hoja, que tiene dos aristas adyacentes a la $K_{2,2}$, que se puede hacer en dos nonisomorphic maneras. Nota ahora que tenemos sólo uno de los bordes restantes, por lo que no podemos añadir otro vértice, ya que esto sería una hoja. Por lo tanto, $G$ tiene exactamente cinco vértices. El último borde puede ser añadido a los dos nonisomorphic seis de borde de gráficos en un total de cuatro nonisomorphic formas (dos para cada uno - usted puede comprobar los casos). Para cada uno de estos candidatos, es fácil encontrar un hueco para colorear que evita un monocromático $K_{2,2}$.