Изменения

Пусть <tex>G</tex> <tex>-</tex> произвольный связный обыкновенный <tex>(n, m)</tex><tex>-</tex>граф, <tex>n \ge 2</tex> и <tex>I</tex> <tex>-</tex> матрица инцидентности какой-либо ориентации графа <tex>G</tex>. Заметим, что <tex>m \ge n - 1</tex> в силу связности графа <tex>G</tex>. По [[Связь матрицы Кирхгофа и матрицы инцидентности|лемме]] выполняется <tex>B = B(G) = I \cdot I^T</tex>. Пусть <tex>B'</tex> <tex>-</tex> подматрица матрицы <tex>B</tex>, полученная удалением последней строки. Тогда имеем <tex>B' = JJ^T</tex>, где <tex>J</tex> <tex>-</tex> это <tex>((n - 1) \times m)</tex> <tex>-</tex> матрица. Очевидно, <tex>B_{nn} = det B'</tex> есть алгебраическое дополнение элемента <tex>\beta_{nn}</tex> в матрице Кирхгофа <tex>B</tex>. В силу формулы Бине-Коши <tex>B_{nn}</tex> равно сумме квадратов всех миноров порядка <tex>(n - 1)</tex> матрицы <tex>J</tex>. Согласно лемме, доказанной выше, каждый такой минор <tex>M</tex> равен <tex>\pm 1</tex>, если остовный подграф графа <tex>G</tex>, ребра которого соответствуют столбцам, вошедшим в матрицу минора <tex>M</tex>, является деревом, и равен <tex>0</tex> в другом случае. Следовательно, <tex>B_{nn}</tex> равно числу остовов графа <tex>G</tex>. Осталось отметить, что по лемме алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.