Изменения

Пусть <mathtex>K</mathtex>- матрица Кирхгофа графа <mathtex>G</mathtex>, <mathtex>I</mathtex>- матрица инцидентности с некоторой ориентацией. Тогда <mathtex>K = I \cdot I^T.</mathtex>

При умножении i-й строки исходной матрицы <mathtex>I</mathtex> на j-й столбец трансонированной ей матрицы <mathtex>I^T </mathtex> перемножаются i-я и j-я строки исходной матрицы. При умножении i-й строки саму на себя на диагонали полученной матрицы будет сумма квадратов элементов i-й строки, которая равна, очевидно, <mathtex>deg(v_i)</mathtex>. Пусть теперь <mathtex>i \ne j</mathtex>. Если <mathtex> (v_i, v_j) \in E </mathtex>, то существует ровно одно ребро, соединяющее <mathtex> v_i </mathtex> и <mathtex> v_j </mathtex>, следовательно результат перемножения i-й и j-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.