Teorema de Kirchhoff

En el campo matemático de la teoría de grafos, el teorema de Kirchhoff, nombrado por Gustav Kirchhoff es un teorema sobre el número de árboles de expansión en un grafo, mostrando que ese número puede ser computado en tiempo polinomial como el determinante de una matriz derivada del grafo. Es una generalización de la fórmula de Cayley que provee el número total de árboles de expansión en un grafo completo.

El número de árboles abarcadores de un grafo ${displaystyle {G}}$ coincide con un cofactor cualquiera de la matriz ${displaystyle {A}_{G}-{D}_{G}}$, donde ${displaystyle {A}_{G}}$ es la matriz de adyacencia y ${displaystyle {D}_{G}}$ es la matriz diagonal cuyas entradas son los grados de los vértices del grafo ${displaystyle {G}}$.