Demostración de que un grafo bipartito tiene elementos nulos en la diagonal de su matriz de adyacencia

Dem: Sea G = (V, E) un grafo.

Entonces probaremos que:⇒

PD: Si un grafo es bipartito entonces para todo n impar los elementos de la diagonal de An son nulos.

Dem: En efecto, si G es bipartito (y simple) sabemos que en la diagonal de la matriz de adyacencia tendrá solo ceros. Luego, para A^n, con n impar mayor a 1, tenemos que los elementos de la diagonal representan cuántos caminos existen que comiencen y terminen en el mismo nodo tal que su largo sea n. Como G es bipartito, sabemos que en G no hay ciclos de largo impar, por lo que todos los elementos de la diagonal serán 0.

PD: Si para todo n impar los elementos de la diagonal de A^n son nulos entonces el grafo es bipartito.

Dem: En efecto, si para todo n impar los elementos de la diagonal de A^n son nulos, esto es equivalente a decir que el grafo en cuestión no tiene ciclos de largo impar, lo cual equivale a decir que el grafo es bipartito.