Файл:Duals graphs.svgПланарный граф и двойственный ему. Любой цикл в голубом графе является минимальным сечением красного графа и наоборот, так что эти два графа алгебраически двойственны и имеют двойственные графовые матроиды.
В терминах чисто теории графов этот критерий можно сформулировать следующим образом: должен существовать другой (двойственный) граф G'=(V',E') и биективное соответствие между рёбрами E' и рёбрами E исходного графа G, такое, что подмножество T рёбер E образует остовное дерево графа G тогда и только тогда, когда рёбра, соответствующие дополнению множества E-T образуют остовное дерево графа G'.
Эквивалентная форма критерия Уитни гласит, что граф G планарен тогда и только тогда, когда он имеет двойственный граф, графовый матроид которого двойственен графовому матроиду графа G.
Граф, графовый матроид которого двойственен графовому матроида графа G, известен как алгебраически двойственный граф для графа G. Тогда критерий планарности Уитни можно перефразировать следующим образом: граф планарен тогда и только тогда, когда у него есть алгебраически двойственный граф.
Топологическая двойственность
Если граф вложен в топологическую поверхность, такую как плоскость, таким образом, что любая грань при вложении является топологическим диском, тогда двойственный граф вложения определяется как граф (в некоторых случаях — мультиграф) H, который имеет вершину для каждой грани вложения и ребро для каждой пары смежных граней.
Согласно критерию Уитни следующие условия эквивалентны:
Поверхность, на которой существует вложение, топологически эквивалентна плоскости, сфере или проколотой плоскости
Граф H алгебраически двойственен G
Любой простой цикл в G соответствует минимальному сечению в графе H, и наоборот
Любой простой цикл в H соответствует минимальному сечению в графе G, и наоборот
Можно определить двойственные графы графа, вложенного в неплоские поверхности, такие как тор, но такие двойственные графы, в общем случае, не имеют соответствия с сечениями, циклами и остовными деревьями, которое требует критерий Уитни.
Шаблон:Статья. См., в частности, стр. 5–6 раздела 2.5 "Bon-matroid of a graph", стр. 19–20 раздела 5.6 "Graphic and co-graphic matroids" и стр. 38–47 раздела 9 "Graphic matroids"
