Un gráfico sin bucles no puede ser bueno.
Supongamos lo contrario, que GG tienen nn vértices y ser bueno.
Dejemos que AA sea la matriz de adyacencia de GG , dejemos que λ1,…,λnλ1,…,λn sean sus valores propios sobre alguna extensión de F2F2 . Tenemos ∑ni=1λi=trA=0∑ni=1λi=trA=0 .
Que AA es bueno significa que AℓAℓ es una matriz todo-1 sobre F2F2 . Tiene rango 1, por lo que al menos n−1n−1 valores propios de AℓAℓ son 0. Por otro lado, los valores propios de AℓAℓ son λℓ1,…,λℓnλℓ1,…,λℓn . Por lo tanto, al menos n−1n−1 λiλi son cero, y como ∑λi=0∑λi=0 , todos λiλi son 0. Por lo tanto AA es nilpotente. Como AℓAℓ tiene rango 1, obtenemos Aℓ+1=0Aℓ+1=0 (de hecho, denota imAℓ:=XimAℓ:=X entonces dimX=1dimX=1 . Tenemos imAℓ+1⊂imAℓ=XimAℓ+1⊂imAℓ=X y también imAℓ+1=AXimAℓ+1=AX . Desde dimX=1dimX=1 , ya sea imAℓ+1={0}imAℓ+1={0} o AX=imAℓ+1=XAX=imAℓ+1=X En este último caso AA no es nilpotente ya que AkX=X≠{0}AkX=X≠{0} para todos k=0,1,2,…k=0,1,2,… ). Así que, A⋅Aℓ=0A⋅Aℓ=0 , lo que significa que la suma de las entradas en cada fila de AA es par, es decir, cada vértice de GG debe tener un grado parejo.
Ahora elige un vértice vv y que WW sea el conjunto de todos los paseos de longitud ℓℓ de vv a vv . La cardinalidad de WW es impar por hipótesis. La operación ρρ de invertir un paseo es una involución en WW por lo que el número de puntos fijos de ρρ es impar; estos puntos fijos consisten en paseos de la forma "tomar cualquier paseo de longitud ℓ/2ℓ/2 a partir de vv y luego volver sobre sus pasos hasta vv " (así en particular, ℓℓ 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 ℓ/2ℓ/2 por lo que el número total de paseos de longitud ℓ/2ℓ/2 debe ser uniforme. Esto es una contradicción.