¿Es correcta esta demostración del Teorema de Graham-Pollak?

Question

El teorema de Graham-Pollak es un teorema de la teoría de grafos. Este teorema supone que hay n naciones (digamos que tenemos 6 naciones: A, B, C, D, E y F). El teorema afirma entonces que todas las peleas entre las naciones se pueden cubrir en al menos n-1 batallas. Pero, ¿qué es un combate y qué es una batalla? Un combate es básicamente una nación contra otra nación (ejemplo: A contra B, B contra C, etc.). Una batalla es lo mismo pero pueden participar varias naciones (ejemplos: A, B y C contra D, C y D contra E y F etc.). Pero, ¿qué tiene esto que ver con la teoría de grafos? En términos matemáticos, el teorema de Graham-Pollak afirma que las aristas de un grafo completo de n vértices no pueden dividirse en menos de n-1 grafos bipartitos completos. Sin embargo, la definición más intuitiva del teorema es adecuada para esta demostración. Así que ahora, vamos a continuar con la prueba real.

Observa que la primera batalla divide a las naciones en 3 grupos: las naciones que lucharon en el primer bando de la batalla (G_1), las naciones que lucharon en el segundo bando de la batalla (G_2) y las naciones que no participaron en la batalla (G_3). Nota: utilizaré m(G_i) para indicar el número de miembros de G_i. Hay 2 tipos de batallas: batallas internas (batallas entre naciones que forman parte del mismo grupo) y batallas externas (batallas entre grupos diferentes). Observamos que hay 3 batallas externas que deben llevarse a cabo: G_1 contra G_2 (la primera batalla), G_1 contra G_3 y G_2 contra G_3. Los 2 últimos combates pueden combinarse en G_1 y G_2 vs G_3. Así obtenemos que el número mínimo de combates externos es 2 (si cada grupo fuera una nación, entonces podemos ver fácilmente que tendría que haber al menos 2 batallas ). Ahora sólo tenemos que averiguar el número de combates internos. Aquí es donde empieza la inducción matemática.

Tenemos que demostrar que el número total de batallas es al menos el número de naciones - 1. En primer lugar, podemos observar fácilmente que el caso base, 1 nación, requiere al menos 0 batallas. Entonces, nuestro segundo paso es demostrar que, si sabemos que k naciones requieren k-1 batallas, entonces k+1 naciones requieren k batallas. Aquí es donde empezamos a tener un sistema de desigualdades. Primero, sabemos que para cualquier grupo G_i, m(G_i)< k+1 (cada batalla tiene al menos una nación en cada bando, así que no puede haber un grupo que contenga todas las naciones, aunque G_3 puede tener 0 naciones, pero sólo si cada nación participa en la primera batalla). Por eso, sabemos que todas las batallas internas de un grupo G_i requieren al menos m(G_i) - 1 batallas (la única excepción es cuando m(G_3) = 0, pero entonces nos quedamos con sólo 2 grupos y obtenemos una prueba similar). También sabemos que m(G_1)+m(G_2)+m(G_3)= k+1 (los grupos no se solapan, y cada nación forma parte de un grupo).

El número total de batallas >= 2 batallas externas + el número mínimo de batallas internas. Pero el número mínimo de batallas internas no es más que la suma del número mínimo de batallas requeridas por cada grupo. Así que vemos que T (el número total de batallas)>=2+m(G_1)-1+m(G_2)-1+m(G_3)-1=m(G_1)+m(G_2)+m(G_3)-1. Pero m(G_1)+m(G_2)+m(G_3)= ¡k+1 (de arriba)! Sustituyendo eso, obtenemos T>=k+1-1=k, así que T>=k. Pero lo que acabamos de demostrar es lo que necesitábamos demostrar.

Una nota final: Sé que esta prueba puede haber omitido algunas cosas, y reconozco que la prueba puede estar equivocada. Por eso hago la pregunta, para ver si la prueba es correcta.

Answer 1

Si de hecho pudiéramos dividir limpiamente todas las batallas en "internas" y "externas", entonces la prueba estaría bien. Pero no podemos.

Cada lucha (es decir, cada arista del grafo completo) puede clasificarse como interna (una arista entre dos vértices del mismo $G_i$ ) o externa (una arista entre dos vértices en $G_i, G_j$ con $i\ne j$ ). A batalla Sin embargo, puede incluir combates de ambos tipos.

Olvidándonos por un momento de las luchas externas, vemos que nos conviene tener estas batallas mixtas. Supongamos que

• Uno de nuestros pasos en la programación de todas las peleas internas para $G_1$ es tener una batalla entre conjuntos $A,B \subseteq G_1$ .
• Uno de nuestros pasos en la programación de todas las peleas internas para $G_3$ es tener una batalla entre conjuntos $C,D \subseteq G_3$ .

Entonces podríamos lograr ambos objetivos a la vez y tener una batalla con $A \cup C$ por un lado y $B \cup D$ por el otro. La inducción dice que necesitamos al menos $|G_i|-1$ batallas por todas las luchas internas a $G_i$ para $i=1,2,3$ . Sin embargo, no es necesario $(|G_1|-1) + (|G_2|-1) + (|G_3|-1)$ batallas en total, porque podemos combinar algunas de las batallas.

La razón por la que esto no refuta a Graham-Pollak es que pagamos por esta eficiencia de una manera diferente. Si combinamos algunas de las batallas internas en batallas mixtas, entonces ya no podemos tener una gran batalla externa de $G_1 \cup G_2$ vs. $G_3$ Algunas de esas peleas ya se han producido.

Según el teorema de Graham-Pollak. debe ser el caso que al cubrir todas las peleas restantes entre $G_1 \cup G_2$ y $G_3$ gastamos todas las batallas que nos ahorramos teniendo batallas mixtas. Pero esto no es en absoluto obvio.

Su prueba no aborda esta cuestión en absoluto: asume que si la primera batalla es $G_1$ vs. $G_2$ entonces $G_3 = \varnothing$ o bien una batalla $G_1 \cup G_2$ vs. $G_3$ sucederá. Esta suposición es falsa. Por ejemplo, la solución siguiente (tomada de Wikipedia ) no tiene esta propiedad, independientemente de la batalla que elijas para definir la primera batalla. $G_1, G_2, G_3$ .