Uporaba teorije grafov
Ravni grafi
Za graf G pravi, da je ravninski, če ga je mogoče na ravnini predstavljati tako, da so vrhovi različne točke, robovi so preproste krivulje in nobena dva roba se med seboj ne srečujeta, razen na njihovih sponkah. Na primer, K 4, celoten graf na štirih točkih, je ravninski, kot kaže slika 4A.
Za dva grafa velja, da sta homeomorfna, če lahko oba dobimo iz istega grafa s pododdelki robov. Grafi na sliki 4A in na sliki 4B so na primer homeomorfni.
Graf K m, n je graf, za katerega je nabor opornic mogoče razdeliti na dve podskupini, eno z m ogledi in drugo z n točki. Katerikoli dve točki iste podmnožice nista sosednji, medtem ko sta kateri koli točki različnih podskustov sosednji. Poljski matematik Kazimierz Kuratowski je leta 1930 dokazal naslednji znan teorem:
Potreben in zadosten pogoj, da je graf G ravninski, je, da ne vsebuje podgrafa homeomorfnega niti K 5 niti K 3,3, prikazanega na sliki 5.
Elementarna krčenje grafa G je transformacija G na novo grafa G 1, tako da sta dva sosednja tocki u in υ G nadomestiti z novo tocko wv G 1 in w je sosednji v G 1 z vsemi vozlišči za ki je v G. ali u sosednja z G. Za graf G * se pravi, da je krčenje G, če je G * mogoče dobiti iz G z zaporedjem osnovnih kontrakcij. Sledi še ena karakterizacija ravninskega grafa zaradi nemškega matematika K. Wagnerja leta 1937.
Graf je ravninski, če in le, če ga ni mogoče skleniti s K 5 ali K 3,3.
Težava s štirimi barvnimi zemljevidi
Rešitev problema s štirbarvnimi zemljevidi je več kot stoletje izmikala vsakemu analitiku, ki je poskusil. Težava je morda pritegnila pozornost Möbiusa, toda zdi se, da je prva pisna omemba pisma enega Francisca Guthrieja njegovemu bratu, študentu Augustusa De Morgana, leta 1852.
Težava se nanaša na ravninske karte - to je razdelitev ravnine na območja, ki se ne prekrivajo, omejena s preprostimi zaprtimi krivuljami. Na geografskih zemljevidih je bilo ugotovljeno empirično, v toliko posebnih primerih, kot je bilo preizkušeno, da so vsaj štiri barve potrebne za obarvanje regij, tako da sta dve regiji, ki imata skupno mejo, vedno obarvani drugače, in v določeni primeri, da so potrebne vsaj štiri barve. (Za regije, ki se srečajo le na določeni točki, na primer zvezni državi Kolorado in Arizona v ZDA, ne velja, da imajo skupno mejo). Formalizacija tega empiričnega opazovanja pomeni tisto, kar imenujemo "štirisobni izrek." Težava je v tem, da dokažemo ali ovržemo trditev, da to velja za vsak ravninski zemljevid. Da tri barve ne bodo dovolj, je enostavno pokazati, medtem ko je zadostnost petih barv leta 1890 dokazal britanski matematik PJ Heawood.
Leta 1879 je angleški Anglec AB Kempe predlagal rešitev štiribarvnega problema. Čeprav je Heawood pokazal, da je Kempejeva trditev napačna, sta se v poznejših preiskavah dva njena koncepta izkazala za koristna. Ena izmed teh, imenovana neizogibna, pravilno navaja nemožnost izdelave zemljevida, v katerem je vsaka od štirih konfiguracij odsotna (te konfiguracije sestavljajo območje z dvema sosedoma, eno s tremi, eno s štirimi in eno s petimi). Drugi koncept, reduktivnost, je dobil ime po veljavnem dokazu Kempe, da če obstaja zemljevid, ki zahteva vsaj pet barv in vsebuje območje s štirimi (ali tremi ali dvema) sosedoma, potem mora biti zemljevid, ki zahteva pet barve za manjše število regij. Kempejev poskus dokazovanja zmanjšljivosti zemljevida, ki vsebuje regijo s petimi sosedi, je bil zmoten, vendar je bil odpravljen v dokazu, ki sta ga leta 1976 objavila Kenneth Appel in Wolfgang Haken iz ZDA. Njihov dokaz je pritegnil nekaj kritik, ker je bilo treba oceniti 1.936 različnih primerov, od katerih je vsak vključeval kar 500.000 logičnih operacij. Appel, Haken in njihovi sodelavci so zasnovali programe, s katerimi je velik digitalni računalnik lahko upravljal s temi podrobnostmi. Računalnik je za izvedbo naloge potreboval več kot 1000 ur, iz tega izhajajoč uradni dokaz je dolg več sto strani.
Eulerijski cikli in problem Königsberškega mostu
Multigraf G sestoji iz praznega niza V (G) tock in podmnožice E (G) iz niza neurejenih parov različnih elementov V (G) s frekvenco f ≥ 1, pritrjenih na vsak par. Če par (x 1, x 2) s frekvenco f pripada E (G), se vrhovi x 1 in x 2 združita s f robovi.
Eulerov cikel multigrafa G je zaprta veriga, v kateri se vsak rob pojavi točno enkrat. Euler je pokazal, da ima multigraf cikel Eulerija, če in le, če je povezan (razen izoliranih točk) in je število opornikov z liho stopnjo ali nič ali dve.
Ta težava je najprej nastala na naslednji način. Reka Pregel, ki je nastala zaradi sotočja njenih dveh vej, teče skozi mesto Königsberg in teče na obeh straneh otoka Kneiphof. Bilo je sedem mostov, kot prikazuje slika 6A. Meščani so se spraševali, ali je mogoče iti na sprehod in prečkati vsak most enkrat in samo enkrat. To je enakovredno iskanju Eulerovega cikla za multigraf na sliki 6B. Euler je pokazal, da je nemogoče, ker obstajajo štiri točke neparnega reda.
