La conjetura de reconstrucción de grafos plantea una pregunta muy sencilla de decir y muy difícil de cerrar: si borramos un vértice cada vez, ¿podemos recuperar el grafo original? La idea se conoce como reconstrucción de grafos y, aunque suena a rompecabezas matemático, tiene reglas bastante concretas.

Lo primero que sí podemos sacar del conjunto de subgrafos es información básica del grafo original. A partir de ese material, podemos deducir el número de vértices, el número de aristas y también la secuencia de grados. O sea, vemos bastante, pero no todo. Y ahí está la trampa: esos datos ayudan mucho, pero no garantizan una reconstrucción única en general.

La pregunta de fondo no es solo si conseguimos una versión parecida, sino si el conjunto de subgrafos determina de manera única el grafo original, hasta isomorfismo. Dicho de forma más llana, queremos saber si existe una sola respuesta posible o si varias estructuras distintas pueden dar lugar al mismo resultado parcial.

Aquí aparece otra distinción importante: los decks legítimos y los ilegítimos. Un deck legítimo es compatible con algún grafo. En cambio, un deck ilegítimo no puede venir de ninguno, porque choca con datos básicos como el número de vértices o el de aristas. Es un buen recordatorio de que no todo conjunto de piezas encaja, aunque algunas se parezcan bastante.

La conjetura general sigue abierta, pero para algunas familias de grafos sí hay respuesta. En árboles y grafos regulares, la reconstrucción única se conoce. En los grafos planares, en cambio, solo hay resultados parciales. Y eso deja la puerta entreabierta a nuevas ideas y a más de una sorpresa.

También han surgido variantes interesantes: trabajar con decks incompletos, usar conjuntos en lugar de multiconjuntos o estudiar grafos orientados. En este último caso, además, existen contraejemplos infinitos, así que el panorama cambia bastante.

Podemos convertir este reto en un pequeño juego de cartas: repartir varias piezas de un grafo, borrar una en cada ronda y tratar de adivinar la figura original antes de ver la solución. Así, sin darnos cuenta, entrenamos el ojo para pensar en estructuras.

Si nos apetece seguir jugando con estas ideas, podemos visitar JeiJoLand.