Dado ℓ≥1 decimos que un gráfico G es ℓ -bueno si para cada u,v∈G (no necesariamente distintos), el número de paseos de longitud ℓ de u a v es impar. Decimos que un gráfico G es bueno si es ℓ -bueno para algunos ℓ≥1 .
¿Existen los buenos gráficos? Para que quede claro, sólo hablo de grafos simples (que carecen de bucles y aristas múltiples).
Contexto: En el libro de Stanley sobre combinatoria algebraica, el ejercicio 1.13 trata de demostrar una interesante propiedad que se cumple para todos los grafos buenos. Un amigo mío me dijo que después de resolver el ejercicio, se dio cuenta de que no conocía ningún ejemplo de tales grafos. Yo también estoy perplejo sobre si pueden existir tales grafos.
Una búsqueda informática reveló que no existe ninguna con 7 o menos vértices. No tengo claro los detalles de la búsqueda, los hizo mi amigo.