Теорема Вагнера

Теорема Вагнера — характеризация планарных графов тесно связанная с теоремой Понтрягина — Куратовского.

Названна в честь Клауса Вагнера. Теорема утверждает, что конечный граф является планарным тогда и только тогда, когда его миноры не включают ни K5 (полный граф с пятью вершинами), ни K3,3 (коммунальный граф, полный двудольный граф с тремя вершинами в каждой доле).

Теорема была одной из наиболее ранних работ в теории миноров графа и её можно рассматривать как предшественницу теоремы Робертсона — Сеймура.

Источник: Википедия