Теорема Эйлера

Теорема Эйлера: Сумма степеней вершин графа равна удвоенному количеству ребер: .

Для ориентированного графа: .

Доказательство: При подсчете суммы степеней вершин каждое ребро учитывается два раза для одного конца ребра и для другого.

Тема 10. Маршруты в графах. Цепи. Циклы. Расстояние между вершинами. Связность. Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети.