¿Qué quieren decir cuando dicen "un azul $3$-regular subgrafo"?

Question

En la página 4 de la siguiente http://web.mat.bham.ac.uk/D.Kuehn/RamseyGreg.pdf el texto dice:

En cualquier gráfico el número de vértices con grado impar tiene que ser uniforme. Por esta razón no puede existir un rojo 5-regular subgrafo de $K_9$ o un azul 3-regular subgrafo de $K_9$. Esto implica que en un sistema completo de 2 de color del gráfico de la orden de nueve, debe haber al menos un vértice que es incidente a al menos seis roja o, al menos, cuatro azules bordes.

No entiendo por qué "no puede existir..." y por qué en vez de "Esto implica que...". Por ejemplo, si llevo dentro de $K_9$ $K_4$ y pintar todo de azul, no puedo obtener un azul $3$-regular subgrafo? Puede ser que yo no entiendo lo que el autor entiende por "blue $3$-regular subgrafo". Podría alguien aclarar?

Answer 1

Que significa que usted no puede encontrar un subconjunto de aristas que incluye todos los $9$ vértices de $K_9$ es $3$ o $5$ regular. Ciertamente, usted puede encontrar un $5$-regular subgrafo de $K_9$-solo tome $K_6$. Lo que él realmente quiere es justificar la siguiente frase-que en cualquiera de los dos para colorear de $K_9$ hay un vértice con seis o más bordes rojos o un vértice con cuatro o más azul en los bordes. Como cada vértice de $K_9$ tiene el grado $8$, la única manera en que esto podría fallar sería si usted podría partición $K_9$ a una $5$-regular pedazo rojo y un $3$-regular pedazo de color azul. La paridad argumento es suficiente para demostrar que esto no es posible.

Answer 2

Si usted toma un $K_9$ y pintar los bordes de una $K_4$ todo azul (y el resto de los bordes están pintados de color rojo, dicen que recordar que cada arista debe ser pintado de un color u otro), entonces el subgrafo resultante consta de todos los azules bordes no es un 3-regular el gráfico 9 vértices. El gráfico azul, que se define como el grafo inducido por exactamente el conjunto de azul de bordes, es un gráfico que consta de una $K_4$ y 5 vértices aislados, y por lo tanto no contiene un 3-regular subgrafo en el 9 vértices.

Observa que en la $K_9$, cada vértice tiene 8 aristas incidentes. Fijar un determinado vértice $v$, y supongo que ha $b(v)$ azul bordes y $r(v)$ bordes rojos incidente. A continuación,$b(v)+r(v)=8$, para cada vértice $v$. El autor dice que en cualquier rojo-azul para colorear de los bordes de $K_9$, $b(v) \ge 4$ o $r(v) \ge 6$ para algunos vértice $v$. Por si ese no es el caso, entonces cada vértice tiene más de 3 azul y en la mayoría de los 5 bordes rojos incidente, y por lo tanto cada vértice tiene exactamente 3 azules y exactamente 5 bordes rojos incidente (por el requisito de $b(v)+r(v)=8$), lo cual es una contradicción ya que no existe un 3-regular el gráfico 9 vértices (y ya que no existe un 5-regular el gráfico 9 vértices).