В теории графов двувариантный граф — это граф, множество вершин которого можно разделить на две равные части так, что каждая вершина смежна ровно с одной вершиной из другого множества, не содержащего ее. [1] [2] [3] В двумерном графе G с 2 n вершинами существует набор из n независимых ребер, нечетное число которых не лежит на цикле графа G .
Граф Петерсена , показанный ниже, является двувариантным графом: если его разбить на внешний пятиугольник и внутреннюю пятиконечную звезду, каждая вершина на одной стороне разбиения имеет ровно одного соседа на другой стороне разбиения. В более общем смысле то же самое верно для любого обобщенного графа Петерсена, образованного путем соединения внешнего многоугольника и внутренней звезды с одинаковым количеством точек; например, это относится к графу Мёбиуса – Кантора и графу Дезарга .
Однако приведенный ниже график не является двумерным. Какие бы три независимых ребра вы ни выбрали, одно из них является ребром цикла.
Дерево T с 2 n вершинами является двувариантным тогда и только тогда, когда число независимости T равно n или, что то же самое, тогда и только тогда, когда оно имеет совершенное паросочетание . [1]
Аналогично можно определить k -вариантный граф , k ≥ 3. Граф называется k -вариантным, если множество его вершин можно разбить на k равных частей так, что каждая вершина смежна ровно с одной вершиной из любой другой части, не содержащей ее. [2]