Cada persona tiene más de 3 enemigos en un grupo. La demostración de que podemos separar en dos grupos donde una persona va a tener a más de un enemigo en el grupo.

Question

La pregunta que yo vi es la siguiente:

En el Parlamento de Sikinia, cada miembro tiene más de tres enemigos. Demostrar que la casa se puede dividir en dos casas, de modo que cada miembro tiene más de un enemigo en su propia casa.

He construido un gráfico donde cada persona corresponde a un vértice y hay una arista entre ellos, si los dos son enemigos. Entonces traté de color de los vértices de la gráfica utilizando dos colores y quitar los bordes que estaban entre los vértices de diferentes colores. La meta es llegar a un gráfico con el grado máximo de 1. He intentado un par de ejemplos. Parece de entrenamiento bien, pero no sé cómo demostrarlo.

Answer 1

Dividir la casa como más te guste. Deje $E_i$ el número de enemigos persona $i$ tiene en su grupo, y vamos a $E = \sum E_i.$ Para cualquier persona que tenga más de $1$ enemigo en su grupo, es decir, al menos $2$, moverlos a otro grupo, donde se tienen en la mayoría de $1$ enemigo. Esto disminuye el $E.$ Desde $E$ es siempre no negativo, este proceso debe terminar, finalmente, en qué punto de la configuración deseada se alcanza.

Answer 2

La pregunta es ambigua en dos formas: no se nos dice si ser un enemigo es simétrica o asimétrica relación, ni de si el parlamento tiene un valor finito o infinito número de miembros. Voy a demostrar que la afirmación es falsa por relaciones asimétricas, incluso en el caso finito; de hecho, yo les doy una (asimétrica) ejemplo de $15$ de la gente, cada uno con sólo $2$ enemigos, que no pueden ser divididos en dos grupos, en los que cada miembro tiene a más de un enemigo. Por otro lado, si la relación es simétrica, la afirmación es cierto incluso en el caso infinito.

Una relación asimétrica de contraejemplo. Hay $15$ de la gente, llamar a $x_i,y_i,y'_i,z_i,z'_i\ (i=0,1,2).$ a los enemigos de La $x_i$ $y_i,y'_i;$ a los enemigos de la $y_i,y'_i$ $z_i,z'_i;$ a los enemigos de la $z_i,z'_i$ $x_i,x_{i+1}$ (adición módulo $3$). Deje que cada una de las $15$ a las personas a ser de color rojo o azul. A continuación, al menos dos de entre $x_0,x_1,x_2$ tienen el mismo color; sin pérdida de generalidad, supongamos que $x_0,x_1$ son de color rojo. Si bien $z_0$ o $z'_0$ es de color rojo, entonces tenemos un rojo persona con dos rojas a los enemigos; así que podemos suponer que la $z_0,z'_0$ azul. Si bien $y_0$ o $y'_0$ es azul, entonces tenemos un azul de la persona con dos azul enemigos; así que podemos suponer que la $y_0,y'_0$ son de color rojo. Pero, a continuación, $x_0$ es un rojo persona con dos rojas a los enemigos.

El finito simétrica caso. (Ya demostrado en la respuesta por @gatos, que se repite aquí por conveniencia.) Si $G=(V,E)$ es finita grafo grafo con el máximo grado en la mayoría de las $3,$, entonces el conjunto de vértices $V$ se puede dividir en dos conjuntos de $V_1,V_2$, de modo que, para $i=1,2,$ cada vértice en $V_i$ tiene más de un vecino (es decir, "enemigo") en $V_i.$ Esto se puede hacer mediante la elección de una partición que maximiza el número de aristas con un extremo en $_1$ y el otro en $V_2.$ (Este argumento no funciona si $V$ es infinito.)

El infinito simétrica caso. Si $G=(V,E)$ es cualquiera (no necesariamente finita) grafo no dirigido con el máximo grado en la mayoría de las $3,$, entonces el conjunto de vértices $V$ se puede dividir en dos conjuntos de $V_1,V_2$, de modo que, para $i=1,2,$ cada vértice en $V_i$ tiene más de un vecino en $V_i.$ Esto se deduce del caso finito por la costumbre tipo de compacidad argumento, es decir, utilizando el hecho de que el Tychonoff producto de cualquier familia de espacios finitos es compacto.

Answer 3

Voy a dar un contra-ejemplo para el caso de que el enemigo relación no se supone que para ser simétrica (pero se supone que para ser irreflexiva). Imaginar cuatro reinos llamados Norte, Sur, Este y Oeste. Cada reino tiene muchos ciudadanos y un rey y un pretendiente al trono (en realidad, el pretendiente al trono podría ser el único ciudadano, torpe). Los enemigos de cada ciudadano son los tres reyes extranjeros. Los enemigos de cada rey son los dos siguientes en sentido antihorario reyes (Norte del enemigo es el Oeste y Sur), así como su pretendiente al trono (cada rey tiene un enemigo dentro de su propio reino).

Ahora vamos a considerar primero cómo dividir los reyes. Claramente no pueden ir todos en el mismo grupo. También, si se trata de un 3-1 split, a continuación, dos de los tres puede ser feliz porque odian el singleton, pero el tercero de los tres va a odiar a los otros dos, en el de tres, por lo que un 3-1 split no funcionará. Ahora vamos a considerar un 2-2 split, donde los reinos de pareja en dos alianzas. Esto puede funcionar para los reyes, pero vamos a necesitar para hacer una observación: ya sea para la alianza, uno de los rey odia el otro rey (y, posiblemente, ambos odian unos a otros). Por ejemplo, el Norte es emparejado con el Oeste o el Sur que el Norte odia, o con Oriente que odia a los del Norte.

Ahora vamos a considerar la colocación de todos los demás. Todo el mundo además de los reyes (incluyendo los pretendientes) odian a los otros tres reyes. Por lo que cada ciudadano tiene que estar en su propio reyes de la alianza (porque hay dos enemigos de reyes en el de la alianza).

Pero ahora por fin llegamos a una contradicción. En cada alianza, hay un rey que se alía con un rey que él odia. Pero entonces este rey también odia el pretendiente en su propio reino. Por lo tanto él tiene dos personas que él odia.

Usuario cardboard_box encontrado una simplificación. En adición a los demás ciudadanos, además de los pretendientes de ser innecesario, de hecho, puede darse el caso de que todos los pretendientes son uno y el mismo, y que no necesitan odiar a nadie. Pero ya que él está tomando el papel de todos los pretendientes, todos los reyes le odian. Pero ahora que la alianza puede ir? Como antes, las dos alianzas tienen un rey que odia el otro rey en la alianza, y todos los reyes de odio, la farsante, así que él no puede ir en alianza, una contradicción. Por lo tanto sólo cinco personas son necesarias para proporcionar un contraejemplo.