Нагуглил:
Дискретная математика. Часть 3 (Курс лекций). Авторы: Емцева Е.Д., Солодухин К.С.
На
стр.1 вводятся определения графа, если допускаются повторяющиеся рёбра — мультиграф, если допускаются петли — псевдограф.
Похоже, что под графом далее в тексте понимают такой, в котором повторяющихся рёбер и петель нет. Если честно этот момент не очень понял.
Дальше,
стр. 4 даётся определение степени вершины и интересная теорема: В любом однородном графе либо его порядок, либо его степень – четное число (однородный — степени всех его вершин равны). Т.е. как раз наш случай. Имеем, что в нашем случае в графе точно должно быть чётное количество вершин (это к комментарию
выше).