граф МакГи

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами. Граф МакГи — это единственная (3,7)-клетка (наименьший кубический с обхватом 7). Он является наименьшей кубической клеткой, не являющейся графом Мура. Впервые открытый Хорстом Саксом, но не опубликованный, граф назван в честь МакГи (W. F. McGee), который опубликовал результат в 1960 году. Позднее, в 1966 году, Уильям Томас Татт доказал, что это единственная (3,7)-клетка. Известны наименьшие кубические графы с числом скрещиваний 1—8 (последовательность в OEIS), наименьший граф с числом скрещиваний 8 — это граф МакГи. Существует 5 неизоморфных кубических графов порядка 24 с числом скрещиваний 8, один из них — обобщённый граф Петерсена G(12,5), известный также как Граф Науру. Граф МакГи имеет радиус 4, диаметр 4, хроматическое число 3 и хроматический индекс 3. Он также 3-вершинно-связен и 3-рёберно-связен.