Теорема Веблена
У математиці теорема Веблена — твердження про те, що множину ребер скінченного графа можна подати у вигляді об'єднання простих циклів, яке не перетинаються, в тому і тільки в тому випадку, коли будь-яка вершина має парний степінь.
Довів Освальд Веблен[1].
Теорема тісно пов'язана з теоремою Ейлера[2] про те, що скінченний граф має Ейлерів цикл (одиничний, не обов'язково простий, цикл, що покриває всі ребра графа) в тому і тільки в тому випадку, коли граф зв'язний і будь-яка вершина має парний степінь. Більш того, подання графа як об'єднання простих циклів можна отримати з Ейлерового циклу повторюваним поділом обходу на дрібніші цикли в разі наявності в циклі повторюваної вершини. Однак теорема Веблена справедлива і для незв'язних графів і її можна узагальнити на нескінченні графи, в яких кожна вершина має скінченний степінь[3].
Якщо в зліченному нескінченному графі G немає вершин з непарним степенем, його можна подати у вигляді об'єднання неперетинних (скінченних) простих циклів у тому і тільки в тому випадку, якщо будь-який скінченний підграф можна розширити (додаванням ребер і вершин із графа G) Ейлерового графа. Зокрема, будь-який зліченний нескінченний граф з єдиним кінцем, що не має вершин непарного степеня, можна подати як об'єднання циклів, що не перетинаються[3].
- ↑ Veblen, 1912.
- ↑ Euler, 1736.
- ↑ а б Sabidussi, 1964.
- L. Euler. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Imperialis Petropolitanae. — 1736. — Т. 8. — С. 128—140.
- N. L. Biggs, E. K. Lloyd, R. J. Wilson . Graph Theory 1736—1936. — Oxford University Press, 1976.
- Gert Sabidussi . Infinite Euler graphs // Canadian Journal of Mathematics. — 1964. — Т. 16. — С. 821—838. — DOI:.
- Oswald Veblen . An Application of Modular Equations in Analysis Situs // Annals of Mathematics. — 1912. — Т. 14, вип. 1. — С. 86—94. — (Second Series).
