Cтраница 3
Очевидно, что если любой граф содержит такой пятивершинный граф ( или, вообще, любой неплоский граф) в качестве подграфа, то он обязательно неплоский. Примером неплоского графа, который не содержит упомянутого полного графа, является граф в задаче о трех пунктах обслуживания и трех домах), приведенный на рис. 4.3. Будем называть такой граф графом Понтрягина - Куратовского 1-го типа. Граф ы Понтрягина - Куратовского 1-го и 2-го типов позволяют определить наиболее общее условие существования плоского графа. [31]