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

У математиці теорема Веблена — твердження про те, що множину ребер скінченного графа можна подати у вигляді об'єднання простих циклів, яке не перетинаються, в тому і тільки в тому випадку, коли будь-яка вершина має парний степінь.

Довів Освальд Веблен^[1].

Теорема тісно пов'язана з теоремою Ейлера^[2] про те, що скінченний граф має Ейлерів цикл (одиничний, не обов'язково простий, цикл, що покриває всі ребра графа) в тому і тільки в тому випадку, коли граф зв'язний і будь-яка вершина має парний степінь. Більш того, подання графа як об'єднання простих циклів можна отримати з Ейлерового циклу повторюваним поділом обходу на дрібніші цикли в разі наявності в циклі повторюваної вершини. Однак теорема Веблена справедлива і для незв'язних графів і її можна узагальнити на нескінченні графи, в яких кожна вершина має скінченний степінь^[3].

Якщо в зліченному нескінченному графі G немає вершин з непарним степенем, його можна подати у вигляді об'єднання неперетинних (скінченних) простих циклів у тому і тільки в тому випадку, якщо будь-який скінченний підграф можна розширити (додаванням ребер і вершин із графа G) Ейлерового графа. Зокрема, будь-який зліченний нескінченний граф з єдиним кінцем, що не має вершин непарного степеня, можна подати як об'єднання циклів, що не перетинаються^[3].

Див. також

• Базис циклів
• Гіпотеза про подвійне покриття циклами
• Покриття ребер циклами
• Ейлерів матроїд^[en]