Los demás quedan del mismo color

El enunciado, textual: «De una prueba elemental de grafos bicoloreados de la sentencia elemental pura:

Note que la sentencia anterior también es una sentencia elemental de grafos. ¿Puede haber una prueba elemental de grafos de esta sentencia?». La sentencia es la que pide escribir el Ejercicio 15 de la Guía 7, y la prueba es su Ejercicio 25 (d).

01 · Antes de probar: una sentencia sin colores

Leída de afuera para adentro: para cada vértice $x$, si $\forall z(\neg (z=x)\to r(x,z))$ —$x$ está conectado con todos los demás—, entonces $\forall u\forall v((\neg (u=x)\wedge \neg (v=x))\to \neg r(u,v))$: entre los demás no hay ninguna arista. Un vértice que toca a todos deja a los otros sin tocarse entre sí.

Lo que el enunciado hace notar es que la sentencia no menciona $R$. Sólo usa $r$ y $=$, así que es una sentencia de grafos, además de serlo de grafos bicoloreados. Las dos preguntas son sobre las mismas palabras; lo que cambia es qué axiomas se pueden usar. Y piden cosas distintas: la primera, una prueba; la segunda, un sí o un no con su razón.

02 · Las herramientas

La Guía 7 lista los axiomas elementales de grafos bicoloreados sin ponerles nombre. Son tres:

• Airr, ninguno se toca a sí mismo: $\forall x\neg r(x,x)$.
• Asim, las aristas no tienen sentido: $\forall x\forall y(r(x,y)\to r(y,x))$.
• Aprop, las puntas de una arista tienen colores distintos: $\forall x\forall y(r(x,y)\to ((R(x)\wedge \neg R(y))\vee (\neg R(x)\wedge R(y))))$.

Los axiomas elementales de grafos son los dos primeros, y nada más. Y la herramienta de la segunda pregunta está en la misma guía, donde define prueba elemental: como se parte de una estructura de la que sólo se sabe que cumple los axiomas, y cada paso es obvio, la sentencia probada tiene que ser verdadera en todas las estructuras del tipo.

03 · La mariposa: dos maneras de verlo

Con colores. El vértice $x$ tiene un color. Un color obliga al de al lado: cada vecino de $x$ tiene el otro. Si $x$ toca a todos, todos los demás tienen el color opuesto al de $x$, o sea el mismo color entre ellos. Y una arista entre dos del mismo color es justo lo que Aprop prohíbe. Eso es todo el ejercicio.

Con triángulos. Si hubiera una arista entre dos de los demás, $u$ y $v$, junto con $x$ formarían un triángulo: $x$ toca a los dos, y ellos se tocan. Y un grafo bicoloreado no tiene triángulos: es el Ejercicio 25 (b) de la guía, probado entero en Dos pruebas elementales.

Las dos maneras son la misma cuenta. La segunda es más corta de pensar, pero escrita cita un resultado de la guía, y la regla de la cátedra exige enunciarlo y probarlo por separado. Así que el escarabajo hace las dos cosas a la vez: supone la arista $r(u,v)$ por el absurdo y corre adentro la prueba del triángulo, sobre $x$, $u$ y $v$.

De atrás para adelante, las piezas son: dos aristas que da la hipótesis, $r(x,u)$ y $r(x,v)$, tomando $z$ como $u$ y como $v$; la tercera, $r(u,v)$, que se supone; y Aprop en las tres. No hace falta Asim: la hipótesis ya da las aristas en el orden en que Aprop las pide. Tampoco Airr, ni siquiera para el caso $u=v$, que la prueba no separa: ahí $r(u,u)$ choca solo con Aprop.

En la estrella, el centro toca a todos y la sentencia vale: el coloreo pone al centro de un color y a las cuatro puntas del otro, todas iguales. Basta una arista entre dos puntas para que falle, y en ese mismo momento el grafo deja de poder bicolorearse: aparece el triángulo. Contado sobre todos los grafos con rótulos de tres, cuatro y cinco vértices —8, 64 y 1024—, la sentencia falla en 1, 19 y 251, y ninguno de ésos se puede bicolorear. Los que sí se pueden —7, 41 y 376— la cumplen todos.

04 · El escarabajo: la prueba escrita

Prueba. Sea $(G,r,R)$ un grafo bicoloreado fijo pero arbitrario, del cual sólo sabemos que satisface los axiomas elementales de grafos bicoloreados. Sea $a\in G$ fijo pero arbitrario, y supongamos $\forall z(\neg (z=a)\to r(a,z))$. Sean $b,c\in G$ fijos pero arbitrarios, y supongamos $(\neg (b=a)\wedge \neg (c=a))$. Supongamos, por el absurdo, que se da $r(b,c)$.

Lo supuesto sobre $a$, tomando $z$ como $b$, nos dice que $(\neg (b=a)\to r(a,b))$; ya que se da $\neg (b=a)$, se da $r(a,b)$. Lo supuesto sobre $a$, tomando $z$ como $c$, nos dice que $(\neg (c=a)\to r(a,c))$; ya que se da $\neg (c=a)$, se da $r(a,c)$.

• El axioma Aprop, tomando $x$ como $a$ e $y$ como $b$, nos dice que $(r(a,b)\to ((R(a)\wedge \neg R(b))\vee (\neg R(a)\wedge R(b))))$. Ya que se da $r(a,b)$, se da $((R(a)\wedge \neg R(b))\vee (\neg R(a)\wedge R(b)))$.
• El axioma Aprop, tomando $x$ como $a$ e $y$ como $c$, nos dice que $(r(a,c)\to ((R(a)\wedge \neg R(c))\vee (\neg R(a)\wedge R(c))))$. Ya que se da $r(a,c)$, se da $((R(a)\wedge \neg R(c))\vee (\neg R(a)\wedge R(c)))$.
• El axioma Aprop, tomando $x$ como $b$ e $y$ como $c$, nos dice que $(r(b,c)\to ((R(b)\wedge \neg R(c))\vee (\neg R(b)\wedge R(c))))$. Ya que se da $r(b,c)$, se da $((R(b)\wedge \neg R(c))\vee (\neg R(b)\wedge R(c)))$.

Abrimos dos casos, según la primera disyunción.

Caso 1: se da $(R(a)\wedge \neg R(b))$. Ya que se da $R(a)$, no puede darse $(\neg R(a)\wedge R(c))$, por lo cual se da $(R(a)\wedge \neg R(c))$; en particular, $\neg R(c)$. Ya que se da $\neg R(b)$, no puede darse $(R(b)\wedge \neg R(c))$, por lo cual se da $(\neg R(b)\wedge R(c))$; en particular, $R(c)$. Se dan $R(c)$ y $\neg R(c)$, lo cual es una contradicción.

Caso 2: se da $(\neg R(a)\wedge R(b))$. Ya que se da $\neg R(a)$, no puede darse $(R(a)\wedge \neg R(c))$, por lo cual se da $(\neg R(a)\wedge R(c))$; en particular, $R(c)$. Ya que se da $R(b)$, no puede darse $(\neg R(b)\wedge R(c))$, por lo cual se da $(R(b)\wedge \neg R(c))$; en particular, $\neg R(c)$. Se dan $R(c)$ y $\neg R(c)$, lo cual es una contradicción.

Los dos casos agotan la primera disyunción y los dos terminan en contradicción, así que no puede darse $r(b,c)$: se da $\neg r(b,c)$.

Cierre. Hemos probado $((\neg (b=a)\wedge \neg (c=a))\to \neg r(b,c))$. Ya que $b$ y $c$ eran fijos pero arbitrarios, vale $\forall u\forall v((\neg (u=a)\wedge \neg (v=a))\to \neg r(u,v))$. Con esto probamos que lo supuesto sobre $a$ implica esa sentencia, y ya que $a$ era fijo pero arbitrario, vale la sentencia del enunciado. ∎

Las generalizaciones son tres y las tres pasan. $b$ y $c$ no salieron de ninguna elección, y la hipótesis que los nombraba se cerró antes de generalizar; la que sigue abierta, la de $a$, no los menciona. Y $a$ se generaliza recién cuando su hipótesis quedó adentro de la implicación.

El conteo dice lo mismo desde afuera. Sobre todas las estructuras de tres elementos con $r$ y $R$ cualesquiera —4096—, las 98 que cumplen Aprop cumplen la sentencia; sobre cuatro elementos, las 2050 de las 1 048 576. Ni Airr ni Asim hacen falta, y la prueba no los cita.

05 · La segunda pregunta: ¿y sin colores?

No puede haber una prueba elemental de grafos de esta sentencia. Si la hubiera, la sentencia sería verdadera en todo grafo, porque lo que se prueba elementalmente a partir de los axiomas de un tipo vale en todas las estructuras de ese tipo. Alcanza con un grafo donde sea falsa.

El triángulo. Sea $G=\{1,2,3\}$ y $r=\{(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)\}$.

• Es un grafo. $G$ no es vacío; ninguno de $(1,1)$, $(2,2)$, $(3,3)$ está en $r$, así que cumple Airr; y cada par está junto con su recíproco, así que cumple Asim.
• El antecedente vale para $x=1$. Los únicos $z$ distintos de $1$ son $2$ y $3$, y $(1,2)$ y $(1,3)$ están en $r$.
• El consecuente no. Con $u=2$ y $v=3$, los dos son distintos de $1$ y $(2,3)$ está en $r$.

Antecedente verdadero y consecuente falso: la implicación falla en $x=1$, y la sentencia es falsa en este grafo. Luego no es verdadera en todo grafo, y no hay prueba elemental de grafos que la pruebe. ∎

Es el contraejemplo más chico posible: en uno o dos vértices la sentencia vale siempre, y de los 8 grafos con rótulos sobre $\{1,2,3\}$ falla sólo en éste. Y tenía que ser un grafo que no se puede bicolorear —el Ejercicio 14 de la guía lo pide probar para todo grafo con un 3-ciclo—: si el triángulo admitiera un bicoloreo, sería un grafo bicoloreado donde la sentencia falla, y la primera parte diría lo contrario. Lo que la prueba sacó de Aprop es exactamente lo que el triángulo no tiene.

06 · Lo que se lleva a otros ejercicios

La misma sentencia, otra teoría. Una sentencia no es demostrable a secas: es demostrable desde ciertos axiomas. Antes de probar, mirá qué axiomas trae el tipo del enunciado. Acá los colores no aparecen en la sentencia, pero hacen todo el trabajo de la prueba.

Para decir que no hay prueba, se exhibe un modelo. Una estructura que cumple los axiomas y donde la sentencia es falsa. Es la misma jugada de la distributiva con el diamante, al revés: allá el contraejemplo mostraba que no se podía probar la igualdad; acá muestra que esta sentencia no se puede probar sin Aprop.

El ejercicio vecino. El 25 (c) de la Guía 7 es la mitad coloreada de éste: si $x$ es rojo y toca a todos, ningún otro es rojo. Sale con la primera mitad del Caso 1.

Lo que hace perder puntos. Citar «un grafo bicoloreado no tiene triángulos», o el lema de la página 15, sin enunciarlo y probarlo aparte. Responder la segunda pregunta con «no, porque la prueba usa Aprop»: que esta prueba lo use no impide que haya otra que no; la razón es el grafo donde la sentencia falla. Dar un contraejemplo que no es un grafo —con un lazo, o con una arista en un solo sentido—. Y generalizar sobre $b$ y $c$ con su hipótesis todavía abierta.

Para tener a mano

1. Si $x$ toca a todos, los demás tienen todos el color opuesto al de $x$: el mismo entre ellos, y entre iguales no hay aristas.
2. Escrita: suponer $r(b,c)$, sacar $r(a,b)$ y $r(a,c)$ de la hipótesis, Aprop en los tres pares, dos casos según el color de $a$, contradicción en $c$.
3. Sólo Aprop: ni Airr ni Asim. Ningún lema citado.
4. Sin colores no hay prueba: el triángulo es un grafo, el centro toca a todos, y los otros dos se tocan.
5. «No puede haber prueba» se justifica con un modelo de los axiomas donde la sentencia es falsa, no con que la prueba conocida usa algo más.