Понятие алгебраического дополнения используется в теории графов для определения числа остовных деревьев и помеченных остовов графа. 1

Согласно теореме Кирхгофа, число остовных деревьев в связном графе порядка n (n │ 2) равно алгебраическому дополнению любого элемента матрицы Кирхгофа. 1 В связном помеченном графе все алгебраические дополнения матрицы Кирхгофа равны между собой и определяют общее число помеченных остовов графа. 1

Также понятие дополнения графа служит инструментом для представления о свойствах графа, которые не сразу видны из исходного графика. 2 Исследуя, какие пары вершин не связаны напрямую, можно получить более глубокое понимание шаблонов связности, возможностей раскраски графа и структурных характеристик. 2