клетка

n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим, если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём. Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее . * 3-клетка — К4, остов тетраэдра, 4 вершины. * 4-клетка — К3,3, один из двух минимальных не планарных графов, 6 вершин. * 5-клетка — Граф Петерсена, 10 вершин. Минимальный кубический граф с индексом самопересечения 2. * 6-клетка — Граф Хивуда, 14 вершин. Разбивается на 1-факторы (то есть, реберно раскрашиваем), любая сумма двух факторов образует гамильтонов цикл. Минимальный кубический граф с индексом самопересечения 3. * 7-клетка — Граф МакГи, 24 вершины. Минимальный кубический граф с индексом самопересечения 8. * 8-клетка — Граф Татта — Коксетера, 30 вершин.