Домики и колодцы: кружка⁠

Пори­со­вав, можно убе­диться, что невозможно отме­тить на плос­ко­сти $5$ точек и соеди­нить каж­дую с каж­дой непе­ре­се­кающи­мися путями: граф $K_5$ — пол­ный граф на $5$ верши­нах — также не явля­ется пла­нар­ным.

Ясно, что раз непла­на­рен граф $K_5$, то непла­на­рен и любой содержащий его граф: напри­мер, пол­ный граф на $N$ верши­нах при $N > 5$. То же можно ска­зать про граф, содержащий $K_{3,3}$. Заме­ча­тельно, что по сути это един­ствен­ные препят­ствия к пла­нар­но­сти! Это утвер­ждает тео­рема Кура­тов­ского $(1930)$: граф явля­ется пла­нар­ным тогда и только тогда, когда он не содержит подграфа, полу­чающегося из $K_5$ или $K_{3,3}$ под­раз­би­е­нием рёбер.

С топо­логи­че­ской точки зре­ния поверх­ность кружки явля­ется тором (поверх­но­стью буб­лика). В тор можно, как гово­рят, «вложить» граф $K_{3,3}$, можно в него вложить и граф $K_5$. И даже граф $K_7$ может быть нари­со­ван на торе — это по сути пред­став­лено в фильме ⁠⁠Рас­краски и многогран­ники. Пере­ход от рас­кра­сок к графам такой: внутри «страны» каж­дого из $7$ цве­тов ста­вится по вершине, а рёбра про­во­дятся через участки общей гра­ницы.

Конечно, и на торе можно нари­со­вать совсем не любой граф (проще всего это понять при помощи вер­сии формулы Эйлера для тора). Из тео­ремы Роберт­со­на—­Сеймура сле­дует, что суще­ствует опи­са­ние графов, вложимых в какую-то кон­крет­ную поверх­ность, в духе тео­ремы Кура­тов­ского — предъяв­ле­нием графов, кото­рые нельзя нари­со­вать на ней. Но даже для тора минималь­ный спи­сок препят­ствий состоит уже не из двух графов, а более чем из $10\,000$ (и не все они ещё най­дены). А вот сде­лать матема­ти­че­ский суве­нир, нари­со­вав или рас­пе­ча­тав на кружке три домика и три колодца, можно уже сей­час.