Теорема Веблена

В математике теорема Веблена, доказанная Вебленом^[1], утверждает, что множество рёбер конечного графа можно представить в виде объединения непересекающихся простых циклов в том и только в том случае, когда любая вершина имеет чётную степень. Таким образом, эта теорема тесно связана с теоремой Эйлера^[2], о том, что конечный граф имеет эйлеров цикл (единичный, не обязательно простой, цикл, покрывающий все рёбра графа) в том и только в том случае, когда граф связен и любая вершина имеет чётную степень. Более того, представление графа в виде объединения простых циклов можно получить из эйлерового цикла путём повторяющегося деления обхода на более мелкие циклы в случае присутствия в цикле повторяющейся вершины. Однако теорема Веблена справедлива и для несвязных графов и может быть обобщена на бесконечные графы, в которых каждая вершина имеет конечную степень^[3].

Если в счётном бесконечном графе G нет вершин с нечётной степенью, он может быть представлен в виде объединения непересекающихся (конечных) простых циклов в том и только в том случае, если любой конечный подграф можно расширить (путём добавления рёбер и вершин из графа G) до эйлерового графа. В частности, любой счётный бесконечный граф с единственным концом^[англ.], не имеющий вершин нечётной степени, может быть представлен как объединение непересекающихся циклов^[3].

См. также

• База циклов
• Гипотеза о двойном покрытии циклами
• Эйлеров матроид^[англ.]