график Петерсена

график Петерсена
график Петерсена
	График Петерсена чаще всего изображают в виде пятиугольника с пентаграммой внутри и пятью спицами.
Назван в честь	Юлиус Петерсен
Вершины	10
Края	15
Радиус	2
Диаметр	2
Обхват	5
Автоморфизмы	120 (С 5 )
Хроматическое число	3
Хроматический индекс	4
Дробный хроматический индекс	3
Род	1
Характеристики	Кубический ; Сильно регулярный ; Дистанционно-транзитивный ; Снарк
	Таблица графиков и параметров

В математической области теории графов граф Петерсена представляет собой неориентированный граф с 10 вершинами и 15 ребрами . Это небольшой граф, который служит полезным примером и контрпримером для многих задач теории графов. Граф Петерсена назван в честь Юлиуса Петерсена , который в 1898 году сконструировал его как наименьший без мостов кубический граф и без трехрёберной раскраски. ^[1]^[2]

Хотя обычно этот график приписывают Петерсену, на самом деле он впервые появился 12 лет назад в статье А. Б. Кемпе ( 1886 ). Кемпе заметил, что ее вершины могут представлять десять линий конфигурации Дезарга , а ее ребра представляют собой пары прямых, не пересекающихся ни в одной из десяти точек конфигурации. ^[3]

Дональд Кнут утверждает, что граф Петерсена представляет собой «замечательную конфигурацию, которая служит контрпримером многим оптимистическим предсказаниям о том, что может быть верно для графов в целом». ^[4]

Граф Петерсена также появляется в тропической геометрии . Конус над графом Петерсена естественным образом отождествляется с пространством модулей пятиточечных рациональных тропических кривых.

Конструкции [ править ]

График Петерсена дополнением линейного графика является $K_{5}$ . Это также граф Кнезера. $KG_{5,2}$ ; это означает, что он имеет одну вершину для каждого 2-элементного подмножества 5-элементного множества, а две вершины соединены ребром тогда и только тогда, когда соответствующие 2-элементные подмножества не пересекаются друг с другом. В виде графа Кнезера вида $KG_{2n-1,n-1}$ это пример странного графика .

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

Вложения [ править ]

Граф Петерсена непланарен . Любой непланарный граф имеет минорами либо полный граф $K_{5}$ , или полный двудольный граф $K_{3,3}$ , но в графе Петерсена оба являются минорами. $K_{5}$ краев минор можно образовать путем стягивания идеально совпадающих , например пяти коротких ребер на первом рисунке. $K_{3,3}$ минор может быть сформирован путем удаления одной вершины (например, центральной вершины 3-симметричного рисунка) и стягивания ребра, инцидентного каждому соседу удаленной вершины.

Самый распространенный и симметричный плоский рисунок графа Петерсена в виде пентаграммы внутри пятиугольника имеет пять пересечений. Однако это не лучший рисунок для минимизации пересечений; существует еще один рисунок (показанный на рисунке) только с двумя пересечениями. Поскольку он неплоский, он имеет по крайней мере одно пересечение на любом рисунке, и если пересекающее ребро удалено из любого рисунка, оно остается неплоским и имеет еще одно пересечение; следовательно, его число пересечений равно 2. Каждое ребро на этом рисунке пересекается не более одного раза, поэтому граф Петерсена является 1-планарным . На торе граф Петерсена можно нарисовать без пересечений ребер; поэтому он имеет ориентируемый род 1.

Граф Петерсена также можно нарисовать (с пересечениями) на плоскости так, чтобы все ребра имели одинаковую длину. То есть это граф единичных расстояний .

Простейшей неориентируемой поверхностью , на которую можно вложить без пересечений граф Петерсена, является проективная плоскость . Это вложение, задаваемое полудодекаэдрической конструкцией графа Петерсена (показано на рисунке). Вложение проективной плоскости также можно сформировать из стандартного пятиугольного рисунка графа Петерсена, поместив перемычку внутри пятиконечной звезды в центре рисунка и проведя края звезды через эту перемычку; полученный рисунок имеет шесть пятиугольных граней. Эта конструкция образует регулярное отображение и показывает, что граф Петерсена имеет неориентируемый род 1.

Граф Петерсена и связанная с ним карта, вложенные в проективную плоскость . Противоположные точки на окружности идентифицируются, что дает замкнутую поверхность неориентируемого рода 1.

Симметрии [ править ]

Граф Петерсена сильно регулярен (с сигнатурой srg(10,3,0,1)). Он также симметричен , что означает, что он транзитивен по ребрам и вершинам . В более строгом смысле, он транзитивен по 3 дугам: каждый направленный трехреберный путь в графе Петерсена может быть преобразован в любой другой такой путь за счет симметрии графа. ^[5]Это один из 13 кубических дистанционно регулярных графов . ^[6]

Группа автоморфизмов графа Петерсена — это симметрическая группа $S_{5}$ ; действие $S_{5}$ на графе Петерсена следует из его построения в виде графа Кнезера . Граф Петерсена является ядром : каждый гомоморфизм графа Петерсена самому себе является автоморфизмом. ^[7] Как показано на рисунках, рисунки графа Петерсена могут демонстрировать пятистороннюю или трехстороннюю симметрию, но невозможно нарисовать граф Петерсена на плоскости таким образом, чтобы на рисунке была видна полная группа симметрии графа Петерсена. график.

Несмотря на высокую степень симметрии, граф Петерсена не является графом Кэли . Это наименьший вершинно-транзитивный граф, не являющийся графом Кэли. ^[а]

пути Гамильтоновы циклы и

Граф Петерсена имеет гамильтонов путь , но не имеет гамильтонова цикла . Это наименьший кубический граф без мостов без гамильтонова цикла. Он гипогамильтонов , что означает, что, хотя он не имеет гамильтонова цикла, удаление любой вершины делает его гамильтоновым и является наименьшим гипогамильтоновым графом.

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

Известны только пять связных вершинно-транзитивных графов без гамильтоновых циклов: полный граф K ₂ , граф Петерсена, граф Кокстера и два графа, полученные из графов Петерсена и Кокстера заменой каждой вершины треугольником. ^[6] Если G — 2-связный r -регулярный граф с не более чем 3 r + 1 вершинами, то G гамильтонов или G — граф Петерсена. ^[8]

Чтобы убедиться в отсутствии гамильтонова цикла C в графе Петерсена , рассмотрим ребра разреза, отделяющие внутренний 5-цикл от внешнего. Если существует гамильтонов цикл, необходимо выбрать четное число этих ребер. Если выбрано только два из них, их конечные вершины должны быть смежными в двух 5-циклах, что невозможно. Следовательно, выбрано 4 из них. Предположим, что верхняя грань разреза не выбрана (все остальные случаи одинаковы по симметрии). Из 5 ребер внешнего цикла необходимо выбрать два верхних ребра, не выбирать два боковых ребра и, следовательно, необходимо выбрать нижнее ребро. Должны быть выбраны два верхних ребра внутреннего цикла, но это завершает неохватывающий цикл, который не может быть частью гамильтонова цикла. В качестве альтернативы мы также можем описать десятивершинные 3-регулярные графы , которые имеют гамильтонов цикл, и показать, что ни один из них не является графом Петерсена, найдя в каждом из них цикл, который короче любого цикла в графе Петерсена. Любой десятивершинный гамильтонов 3-регулярный граф состоит из десятивершинного цикла До плюс пять аккордов. Если какая-либо хорда соединяет две вершины, находящиеся на расстоянии два или три вдоль C друг от друга, граф имеет 3-цикл или 4-цикл и, следовательно, не может быть графом Петерсена. Если две хорды соединяют противоположные вершины C с вершинами на расстоянии четыре вдоль C , снова возникает 4-цикл. Единственный оставшийся случай — это лестница Мёбиуса, образованная соединением каждой пары противоположных вершин хордой, которая снова имеет 4-период. Поскольку граф Петерсена имеет обхват пять, он не может быть сформирован таким образом и не имеет гамильтонова цикла.

Раскраска [ править ]

Граф Петерсена имеет хроматическое число 3, что означает, что его вершины можно раскрасить в три цвета, но не в два, так что ни одно ребро не соединяет вершины одного цвета. Он имеет раскраску списка в 3 цвета по теореме Брукса для раскраски списков.

Граф Петерсена имеет хроматический индекс 4; для окраски краев требуется четыре цвета. Будучи связным кубическим графом без мостов с хроматическим индексом четыре, граф Петерсена представляет собой снарк . Это наименьший возможный снарк, и он был единственным известным снарком с 1898 по 1946 год. Теорема снарка , результат, выдвинутый У.Т. Туттом и объявленный в 2001 году Робертсоном, Сандерсом, Сеймуром и Томасом, ^[9] утверждает, что каждый снарк имеет граф Петерсена в качестве минора .

Кроме того, граф имеет дробный хроматический индекс 3, что доказывает, что разница между хроматическим индексом и дробным хроматическим индексом может достигать 1. Давняя гипотеза Голдберга-Сеймура предполагает, что это самый большой возможный разрыв.

Число Туэ (вариант хроматического индекса) графа Петерсена равно 5.

Граф Петерсена требует как минимум трех цветов в любой (возможно, неправильной) раскраске, которая нарушает всю его симметрию; то есть его отличительное число равно трем. За исключением полных графов, это единственный граф Кнезера, отличительное число которого не равно двум. ^[10]

Другая недвижимость [ править ]

График Петерсена:

является 3-связным и, следовательно, 3-реберно связным и не имеет мостов. См . глоссарий .
имеет номер независимости 4 и является 3-частным. См . глоссарий .
является кубическим , имеет доминантное число 3, имеет идеальное соответствие и 2-фактор .
имеет 6 различных совершенных паросочетаний.
— наименьший кубический граф обхвата 5. (Это уникальный $(3,5)$ - клетка . Фактически, поскольку он имеет всего 10 вершин, это единственный $(3,5)$ - График Мура .) ^[11]
каждый кубический граф без мостов без минора Петерсена имеет двойное покрытие цикла. ^[12]
— наименьший кубический граф с инвариантом графа Колена де Вердьера µ = 5. ^[13]
— наименьший граф полицейского №3 . ^[14]
имеет радиус 2 и диаметр 2. Это самый большой кубический граф с диаметром 2. ^[б]
имеет 2000 остовных деревьев , больше, чем любой кубический граф с 10 вершинами. ^[15]^[16]^[с]
имеет хроматический полином $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$ . ^[17]
имеет характеристический полином $(t-1)^{5}(t+2)^{4}(t-3)$ , что делает его интегральным графом — графом, спектр которого полностью состоит из целых чисел.

Петерсена раскраске о Гипотеза

Эйлеров подграф графа $G$ — подграф, состоящий из подмножества ребер $G$ , касаясь каждой вершины $G$ четное количество раз. Эти подграфы являются элементами пространства циклов $G$ и иногда называются циклами. Если $G$ и $H$ — любые два графика, функция от ребер $G$ до краев $H$ называется циклически непрерывным, если прообраз каждого цикла $H$ представляет собой цикл $G$ . Гипотеза Йегера утверждает, что каждый граф без мостов имеет циклически непрерывное отображение в граф Петерсена. Джегер показал, что из этой гипотезы следует гипотеза 5 -циклового двойного покрытия и гипотеза Берджа-Фалкерсона». ^[18]

Связанные графики [ править ]

Обобщенный граф Петерсена $G(n,k)$ образуется путем соединения вершин правильного n -угольника с соответствующими вершинами звездчатого многоугольника с символом Шлефли { n / k }. ^[19]^[20] Например, в этих обозначениях граф Петерсена имеет вид $G(5,2)$ : его можно образовать, соединив соответствующие вершины пятиугольника и пятиконечной звезды, а ребра в звезде соединяют каждую вторую вершину. Обобщенные графы Петерсена включают также n -призму $G(n,1)$ график Дюрера $G(6,2)$ , граф Мёбиуса-Кантора $G(8,3)$ , додекаэдр $G(10,2)$ , граф Дезарга $G(10,3)$ и график Науру $G(12,5)$ .

Семейство Петерсена состоит из семи графов, которые могут быть сформированы из графа Петерсена с помощью нуля или более применений преобразований Δ-Y или Y-Δ . Полный граф K6 _также принадлежит семейству Петерсена. Эти графы образуют запрещенные миноры для встраиваемых без связей графов , графов, которые можно встроить в трехмерное пространство таким образом, что никакие два цикла в графе не будут связаны между собой . ^[21]

Граф Клебша содержит множество копий графа Петерсена в виде индуцированных подграфов : для каждой вершины v графа Клебша десять несоседей v индуцируют копию графа Петерсена.

Примечания [ править ]

^ Как уже говорилось, предполагается, что графы Кэли не обязательно должны быть связными. Некоторые источники требуют, чтобы графы Кэли были связными, что делает пустой граф с двумя вершинами наименьшим вершинно-транзитивным графом, не являющимся графом Кэли; согласно определению, данному в этих источниках, граф Петерсена — это наименьший связный вершинно-транзитивный граф, не являющийся графом Кэли.
^ Это следует из того, что это граф Мура, поскольку любой граф Мура является максимально возможным регулярным графом со своей степенью и диаметром. ^[11]
^ Кубические графы с 6 и 8 вершинами, максимизирующие количество остовных деревьев, представляют собой лестницы Мёбиуса .

Ссылки [ править ]

^ Брауэр, Андрис Э. , Граф Петерсена
^ Петерсен, Юлиус (1898), «О теореме Тейта» , L'Intermédiaire des Mathématiciens , 5 : 225–227.
^ Кемпе, AB (1886), «Мемуары по теории математической формы», Philosophical Transactions of the Royal Society of London , 177 : 1–70, doi : 10.1098/rstl.1886.0002 , S2CID 108716533
^ Кнут, Дональд Э., Искусство компьютерного программирования; том 4, предварительный выпуск 0A. Черновой вариант раздела 7: Введение в комбинаторный поиск
^ Бабай, Ласло (1995), «Группы автоморфизмов, изоморфизм, реконструкция», у Грэма, Рональда Л .; Гретшель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , том. I, Северная Голландия, стр. 1447–1540, Следствие 1.8, заархивировано из оригинала 11 июня 2010 г.
^ Jump up to: Перейти обратно: ^а ^б Ройл, Г. «Кубические симметричные графы (перепись Фостера)». Архивировано 20 июля 2008 г. в Wayback Machine.
^ Кэмерон, Питер Дж. (2004), «Автоморфизмы графов», в Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (ред.), Темы алгебраической теории графов , Энциклопедия математики и ее приложений, том. 102, Издательство Кембриджского университета, Кембридж, стр. 135–153, doi : 10.1017/CBO9780511529993 , ISBN. 0-521-80197-4 , МР 2125091 ; см., в частности, стр. 153
^ Холтон, Д.А.; Шихан, Дж. (1993), График Петерсена , издательство Кембриджского университета , стр. 32, ISBN 0-521-43594-3
^ Пегг, Эд-младший (2002), «Рецензия на книгу: Колоссальная книга по математике» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Бибкод : 2002ITED...49.1084A , doi : 10.1109/ТЭД.2002.1003756
^ Альбертсон, Майкл О.; Бутин, Дебра Л. (2007), «Использование определяющих наборов для различения графов Кнезера», Электронный журнал комбинаторики , 14 (1): R20, doi : 10.37236/938 , MR 2285824 .
^ Jump up to: Перейти обратно: ^а ^б Хоффман, Алан Дж .; Синглтон, Роберт Р. (1960), «Графы Мура диаметром 2 и 3» (PDF) , IBM Journal of Research and Development , 5 (4): 497–504, doi : 10.1147/rd.45.0497 , MR 0140437 .
^ Олспах, Брайан ; Чжан, Цунь-Цюань (1993), «Циклические покрытия кубических мультиграфов», Дискретная математика. , 111 : 11–17 .
^ Ласло Ловас, Александр Шрийвер (1998), «Теорема Борсука для антиподальных связей и спектральная характеристика бессвязно встраиваемых графов» (PDF) , Труды Американского математического общества , 126 (5): 1275–1285, doi : 10.1090/S0002 -9939-98-04244-0 , S2CID 7790459
^ Бэрд, Уильям; Беверидж, Эндрю; Бонато, Энтони; Коденотти, Паоло; Маурер, Аарон; МакКоли, Джон; Валева, Сильвия (2014), «О минимальном порядке $графов k$ -cop-win» , Вклад в дискретную математику , 9 (1): 70–84, arXiv : 1308.2841 , doi : 10.11575/cdm.v9i1.62207 , MR 3265753
^ Якобсон Дмитрий; Ривин, Игорь (1999), О некоторых экстремальных задачах теории графов , arXiv : math.CO/9907050 , Bibcode : 1999math......7050J
^ Вальдес, Л. (1991), «Экстремальные свойства остовных деревьев в кубических графах», Congressus Numerantium , 85 : 143–160 .
^ Биггс, Норман (1993), Алгебраическая теория графов (2-е изд.), Кембридж: Cambridge University Press, ISBN 0-521-45897-8
^ ДеВос, Мэтт; Нешетржил, Ярослав ; Распауд, Андре (2007), «О картах ребер, инверсия которых сохраняет потоки или напряжения», Теория графов в Париже , Trends Math., Базель: Birkhäuser, стр. 109–138, doi : 10.1007/978-3-7643-7400 -6_10 , ISBN 978-3-7643-7228-6 , МР 2279171 .
^ Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5 .
^ Уоткинс, Марк Э. (1969), «Теорема о раскрасках Тейта с применением к обобщенным графам Петерсена», Journal of Combinatorial Theory , 6 (2): 152–164, doi : 10.1016/S0021-9800(69)80116 -Х
^ Бейли, Розмари А. (1997), Обзоры по комбинаторике , Cambridge University Press, стр. 187, ISBN 978-0-521-59840-8

Дальнейшее чтение [ править ]

Эксу, Джеффри; Харари, Фрэнк ; Кабелл, Джеральд (1981), «Числа пересечений некоторых обобщенных графов Петерсена», Mathematica Scandinavica , 48 : 184–188, doi : 10.7146/math.scand.a-11910 .
Ловас, Ласло (1993), Комбинаторные задачи и упражнения (2-е изд.), Северная Голландия, ISBN 0-444-81504-Х .
Швенк, AJ (1989), «Перечисление гамильтоновых циклов в некоторых обобщенных графах Петерсена», Журнал комбинаторной теории , серия B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064-6
Чжан, Цунь-Цюань (1997), Целочисленные потоки и циклические покрытия графов , CRC Press, ISBN 978-0-8247-9790-4 .
Чжан, Цунь-Цюань (2012), Двойная обложка графиков , Cambridge University Press, ISBN 978-0-5212-8235-2 .

Внешние ссылки [ править ]

[8] Как уже говорилось, предполагается, что графы Кэли не обязательно должны быть связными. Некоторые источники требуют, чтобы графы Кэли были связными, что делает пустой граф с двумя вершинами наименьшим вершинно-транзитивным графом, не являющимся графом Кэли; согласно определению, данному в этих источниках, граф Петерсена — это наименьший связный вершинно-транзитивный граф, не являющийся графом Кэли.

[16] Это следует из того, что это граф Мура, поскольку любой граф Мура является максимально возможным регулярным графом со своей степенью и диаметром. ^[11]

[19] Кубические графы с 6 и 8 вершинами, максимизирующие количество остовных деревьев, представляют собой лестницы Мёбиуса .

[1] Брауэр, Андрис Э. , Граф Петерсена

[2] Петерсен, Юлиус (1898), «О теореме Тейта» , L'Intermédiaire des Mathématiciens , 5 : 225–227.

[3] Кемпе, AB (1886), «Мемуары по теории математической формы», Philosophical Transactions of the Royal Society of London , 177 : 1–70, doi : 10.1098/rstl.1886.0002 , S2CID 108716533

[4] Кнут, Дональд Э., Искусство компьютерного программирования; том 4, предварительный выпуск 0A. Черновой вариант раздела 7: Введение в комбинаторный поиск

[5] Бабай, Ласло (1995), «Группы автоморфизмов, изоморфизм, реконструкция», у Грэма, Рональда Л .; Гретшель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , том. I, Северная Голландия, стр. 1447–1540, Следствие 1.8, заархивировано из оригинала 11 июня 2010 г.

[foster-6] Jump up to: Перейти обратно: ^а ^б Ройл, Г. «Кубические симметричные графы (перепись Фостера)». Архивировано 20 июля 2008 г. в Wayback Machine.

[7] Кэмерон, Питер Дж. (2004), «Автоморфизмы графов», в Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (ред.), Темы алгебраической теории графов , Энциклопедия математики и ее приложений, том. 102, Издательство Кембриджского университета, Кембридж, стр. 135–153, doi : 10.1017/CBO9780511529993 , ISBN. 0-521-80197-4 , МР 2125091 ; см., в частности, стр. 153

[9] Холтон, Д.А.; Шихан, Дж. (1993), График Петерсена , издательство Кембриджского университета , стр. 32, ISBN 0-521-43594-3

[10] Пегг, Эд-младший (2002), «Рецензия на книгу: Колоссальная книга по математике» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Бибкод : 2002ITED...49.1084A , doi : 10.1109/ТЭД.2002.1003756

[11] Альбертсон, Майкл О.; Бутин, Дебра Л. (2007), «Использование определяющих наборов для различения графов Кнезера», Электронный журнал комбинаторики , 14 (1): R20, doi : 10.37236/938 , MR 2285824 .

[hs60-12] Jump up to: Перейти обратно: ^а ^б Хоффман, Алан Дж .; Синглтон, Роберт Р. (1960), «Графы Мура диаметром 2 и 3» (PDF) , IBM Journal of Research and Development , 5 (4): 497–504, doi : 10.1147/rd.45.0497 , MR 0140437 .

[13] Олспах, Брайан ; Чжан, Цунь-Цюань (1993), «Циклические покрытия кубических мультиграфов», Дискретная математика. , 111 : 11–17 .

[14] Ласло Ловас, Александр Шрийвер (1998), «Теорема Борсука для антиподальных связей и спектральная характеристика бессвязно встраиваемых графов» (PDF) , Труды Американского математического общества , 126 (5): 1275–1285, doi : 10.1090/S0002 -9939-98-04244-0 , S2CID 7790459

[15] Бэрд, Уильям; Беверидж, Эндрю; Бонато, Энтони; Коденотти, Паоло; Маурер, Аарон; МакКоли, Джон; Валева, Сильвия (2014), «О минимальном порядке $графов k$ -cop-win» , Вклад в дискретную математику , 9 (1): 70–84, arXiv : 1308.2841 , doi : 10.11575/cdm.v9i1.62207 , MR 3265753

[17] Якобсон Дмитрий; Ривин, Игорь (1999), О некоторых экстремальных задачах теории графов , arXiv : math.CO/9907050 , Bibcode : 1999math......7050J

[18] Вальдес, Л. (1991), «Экстремальные свойства остовных деревьев в кубических графах», Congressus Numerantium , 85 : 143–160 .

[biggs-20] Биггс, Норман (1993), Алгебраическая теория графов (2-е изд.), Кембридж: Cambridge University Press, ISBN 0-521-45897-8

[21] ДеВос, Мэтт; Нешетржил, Ярослав ; Распауд, Андре (2007), «О картах ребер, инверсия которых сохраняет потоки или напряжения», Теория графов в Париже , Trends Math., Базель: Birkhäuser, стр. 109–138, doi : 10.1007/978-3-7643-7400 -6_10 , ISBN 978-3-7643-7228-6 , МР 2279171 .

[22] Коксетер, HSM (1950), «Самодвойственные конфигурации и регулярные графы», Бюллетень Американского математического общества , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5 .

[23] Уоткинс, Марк Э. (1969), «Теорема о раскрасках Тейта с применением к обобщенным графам Петерсена», Journal of Combinatorial Theory , 6 (2): 152–164, doi : 10.1016/S0021-9800(69)80116 -Х

[Bailey1997-24] Бейли, Розмари А. (1997), Обзоры по комбинаторике , Cambridge University Press, стр. 187, ISBN 978-0-521-59840-8

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[а]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[б]

[15]

[16]

[с]

[17]

[18]

[19]

[20]

[21]