Gráfelmélet - síkbarajzolhatóság?

Ez a részgráf egy K₅:

Első körben töröljük ki a 2 fokszámú csúcsot, mivel az nem befolyásolja a síkbarajzolhatóságot, de a részgráfokat "elrejtheti".
Belátni úgy tudod a legegyszerűbben, hogy kiszínezed a csúcsokat; ha ez a gráf kiszínezhető legfeljebb 4 színnel, akkor K₅ nem lehet benne, mivel a K₅ kromatikus száma 5 (megnéztem, és 3-mal színezhető).
A K3;3 már egy kicsit nehezebb, de lévén, hogy nincs benne túl sok csúcs, könnyen észrevehető, ha van benne.

Színezéshez infó:

Az eredeti tényleg színezhető 3 színnel, pl. úgy, ahogy az első ábra mutatja.
Viszont nem csak 2-élű csúcsokat távolítunk el, amikor a részgráfot csináljuk, hanem éleket is, éz az élek eltávolítása után 2-élűek lesznek korábban többélű csúcsok, ami kétélűeket szintén eltávolítjuk.
(Valójában nem kell eltávolítani, mert akkor is topologikusan izomorf ha ott marad, de ez részletkérdés.)

Szóval eltávolítás után, hogy csak 5 csúcs maradjon, az eredeti színek úgy alakulnak, ahogy a második ábra mutatja. A két sárga egymás mellé kerül, tehát nem színezhető 3 színnel annak ellenére, hogy a bővebb gráf színezhető volt.

Az eredeti gráf kromatikus száma tehát nem mérvadó annak eldöntésénél, hogy van-e benne K₅ részgráf.

Csináltam még néhány rajzot, hogy jobban látszódjon a K₅.

Az első ugyanaz a durva rajz, amit az első válaszomban adtam. Ez a részgráf rajz úgy keletkezett, hogy letöröltem az eredeti gráfból néhány élet, aztán kidobtam néhány csúcsot is. A kidobott csúcsokat úgy jelöltem, hogy a csúcs-gombócoknak a felét letöröltem.

A második rajzban teljesen kihagytam a kidobott csúcsokat, és az oda menő éleket kicsit meggörbítettem, hogy látszódjon még rajtuk, mik voltak eredetileg, de az is jobban látszódjon, hogy honnan hová mennek. Ennél a rajznál könnyebb összeszámolni, hogy minden csúcs fokszáma 4 és két csúcs között nem megy 1-nél több él, vagyis ez tényleg K₅.

A harmadik rajznál a fenti középső csúcsot picit feljebb vittem, az eddigi görbe éleket pedig teljesen kiegyenesítettem. Ez már felismerhetően egy K₅ ábra.

-------
Hogyan találtam ezt a részgráfot? Leírom, közben figyeld az eredeti gráfot meg a mostani első képet is, ahogy olvasod:

A K₅-ben mind az 5 csúcs fokszáma 4. Vagyis amik kisebb fokszámúak, azok a csúcsok biztos nincsenek benne egy K₅ részgráfban. Ezzel 3 csúcs kiesett. Nem szabad azért kidobni őket, mert mit kezdesz akkor az éleikkel, az élekre szükség van még. (Az egy szem 2-es fokszámút ki lehet dobni és a két élet egyesíteni...)
Aztán kiválasztottam 5 csúcsot a maradék 8-ból. Az a gyanúm, ennél a gráfnál szinte mindegy, melyik 5-öt választjuk ki, valószínű mindegyik egy-egy K₅. Amiket választottam, azok úgy adták magukat, "látszott" rajtuk, hogy valószínű jók lesznek.
Aztán megnéztem, melyik csúcsból hány él megy közvetlenül egy másikba az 5 közül. Egyedül a fenti középsőből megy 4, azzal már nem kell foglalkozni. Az alsó kettőből 3-3 él megy, mindkettőhöz kell még 1-1-egy találni, amik a maradék csúcshoz mennek (nem ugyanahhoz...) A bal alsóból 1 köztes csúcson át megy élsorozat a jobb oldaliba, a jobb alsóból viszont már 3 közbelső csúcs is van, hogy eljussunk a bal oldali fentibe.
A fenti két szélsőből eredetileg 2-2 él ment az 5-be, most már 3-3, még egyet kell találni, ami őket kettejüket összeköti. Ez egyszerűen megvan, egyetlen egy köztes csúcs van csak az élsorozatban.

Kész.