Un gráfico sin bucles no puede ser bueno.
Supongamos lo contrario, que $G$ tienen $n$ vértices y ser bueno.
Dejemos que $A$ sea la matriz de adyacencia de $G$ , dejemos que $\lambda_1,\ldots,\lambda_n$ sean sus valores propios sobre alguna extensión de $\mathbb{F}_2$ . Tenemos $\sum_{i=1}^n \lambda_i=\mathrm{tr} A=0$ .
Que $A$ es bueno significa que $A^\ell$ es una matriz todo-1 sobre $\mathbb{F}_2$ . Tiene rango 1, por lo que al menos $n-1$ valores propios de $A^\ell$ son 0. Por otro lado, los valores propios de $A^\ell$ son $\lambda_1^\ell,\ldots,\lambda_n^\ell$ . Por lo tanto, al menos $n-1$ $\lambda_i$ son cero, y como $\sum \lambda_i =0$ , todos $\lambda_i$ son 0. Por lo tanto $A$ es nilpotente. Como $A^\ell$ tiene rango 1, obtenemos $A^{\ell+1}=0$ (de hecho, denota $\mathrm{im} A^{\ell}:=X$ entonces $\dim X=1$ . Tenemos $\mathrm{im} A^{\ell+1}\subset \mathrm{im} A^{\ell}=X$ y también $\mathrm{im} A^{\ell+1}=AX$ . Desde $\dim X=1$ , ya sea $\mathrm{im} A^{\ell+1}=\{0\}$ o $AX=\mathrm{im} A^{\ell+1}=X$ En este último caso $A$ no es nilpotente ya que $A^kX=X\ne \{0\}$ para todos $k=0,1,2,\ldots$ ). Así que, $A\cdot A^\ell=0$ , lo que significa que la suma de las entradas en cada fila de $A$ es par, es decir, cada vértice de $G$ debe tener un grado parejo.
Ahora elige un vértice $v$ y que $W$ sea el conjunto de todos los paseos de longitud $\ell$ de $v$ a $v$ . La cardinalidad de $W$ es impar por hipótesis. La operación $\rho$ de invertir un paseo es una involución en $W$ por lo que el número de puntos fijos de $\rho$ es impar; estos puntos fijos consisten en paseos de la forma "tomar cualquier paseo de longitud $\ell/2$ a partir de $v$ y luego volver sobre sus pasos hasta $v$ " (así en particular, $\ell$ debe ser par). Pero como cada vértice tiene grado par, en particular hay un número par de opciones para el último paso del paseo de longitud $\ell/2$ por lo que el número total de paseos de longitud $\ell/2$ debe ser uniforme. Esto es una contradicción.
