Parece, sin embargo, que la clasificación o búsqueda de grafos fuertemente regulares no es tan fácil en general (ni siquiera para valores no muy grandes de sus parámetros), y la página de Ted Spence nos revela que en un artículo de 1995 él encontró 32,548
Sabiendo esto ya duermo un poco más tranquilo. En mis intentos fallidos, primero demostré que la solución debiera tener cierto número de aristas, y mi cota estaba mal. Luego me pareció encontrar una cota superior que descartaba ¡justamente las soluciones calculadas por Spence! Se imaginarán mi sorpresa al enterarme de que no solo sí hay soluciones de ese tipo, sino que encima hay varios miles de ellas. Al parecer, si las clasificaciones para números pequeños de vértices está completa, no existen las soluciones pequeñas que trataba de construir. Me imaginé que podría ser un grafo de Harary, pero no me atreví a preguntar si cierto parámetro en el problema era una cota inferior o un valor exacto que debía alcanzar el grafo buscado.
Me hace falta muchísima más imaginación :(.
P. D.: Los sevillanos publicaron dos soluciones, una de Alberto Castaño y otra "al más puro estilo de Warren Sánchez" (¡qué simpáticos!). La de Castaño está muy bien y me convence plenamente, no así la que ellos proponen. Castaño reduce el problema a un conteo doble de aristas para obtener un polinomio cuadrático que hay que resolver diofánticamente, y que bien demuestra que las soluciones de Spence son las únicas posibles.
