Bizonyítsuk be, hogy minden v ≥ 4 természetes számhoz létezik egy sík gráf, amelynek v csúcsa van, amelynek minden tartományát a C4 kör (ciklus) határol.?

Ha v=4, akkor triviális, maga a C4 kör teljesíti a feltételt.

Ha v=5, akkor rajzoljunk egy C4 kört, például egy négyzetet, ennek ötödik pontja legyen a négyzet középpontja, ezt összekötjük a négyzet csúcsaival, a behúzásokat hívjuk küllőknek. Kész is van a feltételeknek megfelelő gráf.

Ha v>=6, akkor az előbbi gráf küllőire akárhogyan elszórhatjuk a csúcsokat, a C4 mindig határolni fogja a belső tartományokat.

Mivel a külső, végtelen tartományt is C4 határolja, ezért a gráf összefüggő.

v=4 triviális, egy négyzet teljesíti a feltételt.

Teljes indukcióval tegyük föl, hogy valamely v=n-re már tudunk ilyen gráfot.

Ekkor v=n+1-re: vegyük az n-re jó gráf egy tetszőleges síkbarajzolását, és ennek a végtelen tartományát (de tetszőleges tartománnyal is működik). A v+1. csúcsot helyezzük el a végtelen tartományban, és kössük össze a végtelen tartományt határoló C4 két, nem szomszédos csúccsal, ez lesz a 2 új él. Ekkor az új gráf továbbra is síkgráf. A korábbi véges tartományok nem változtak, így továbbra is C4 határolja őket. Újonnan létrejött egy véges tartomány, amit szintén C4 határol, 4 csúcs az eredeti C4-ről és az új csúcs. Az új végtelen tartomány szintén C4, hasonló megfontolásból. Tehát az új gráf n+1 csúccsal is jó lesz, ezzel kész a teljes indukció.

#1

Nem úgy kell érteni a kérdést, hogy a gráf minden egyes tartományát (élekkel határolt üres területét) külön-külön C4 határolja?

Akkor úgy lehet bővíteni a C4 és a további gráfokat, hogy felrakunk egy külső csúcsot és két olyan külső csúccsal kötjük össze, amiknek a távolsága 2 élnyi.