Некоторые определения, относящиеся к графам

Мультиграф - граф в котором допускается более одного ребра между вершинами. Примером мультиграфа является граф, построенный Эйлером для решения задачи о кенигсбергских мостах - рис.1 и рис.2.

Рис.1
Рис.2

Графы, в которых не допускаются параллельные ребра, то есть кратные ребра между вершинами, иногда называют простыми графами.
Псевдограф - граф, в котором допускается как наличие петель, так и существование более одного ребра между двумя вершинами.
Цикл - путь ненулевой длины, соединяющий вершину саму с собой и не содержащий повторяющихся ребер.
Простой цикл
- цикл соединяющий вершину v саму с собой и не содержащий повторяющихся вершин, кроме v.
Граф называется полным, если любые две его вершины соединены одним ребром.
Степенью вершины называется количество ребер, инцидентных этой вершине.
Цикл, который включает все ребра и вершины графа называется эйлеровым циклом. (По определению цикла путь, составляющий эйлеров цикл, не может проходить дважды по одному и тому же ребру, но может проходить несколько раз через одну и ту же вершину).

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

Доказательство.
Пусть граф имеет эйлеров цикл. Поскольку он связный все его вершины принадлежат циклу. Для каждой из них цикл, проходящий через вершину, вносит 2 в ее степень. Поэтому степень любой вершины - четная.
Обратное утверждение доказывается индуктивно. Легко проверить, что при числе вершин k = 2 и 3 только четные степени вершин обеспечивают наличие эйлерова цикла. Пусть граф с k вершинами, имеющими четную степень, имеет эйлеров цикл. Добавим к нему еще одну вершину с четной степенью. Добавленная вершина должна быть связана общими ребрами с одной или несколькими вершинами старого, чтобы новый граф остался связным. При этом к любой старой вершине, связанной ребрами с новой вершиной, должно подходить четное количество новых ребер, чтобы ее степень осталась четной. Поэтому, дополнив эйлеров цикл для k-вершинного графа заходами в новую вершину из каждой старой вершины, связанной с новой, получим эйлеров цикл для (k+1)-вершинного графа.

Из доказанной теоремы следует невозможность обойти все мосты, изображенные на рис.1, пройдя по каждому из них только один раз.