Síkbeli egyenesek és gráffelbonthatóság

Abstract

Szakdolgozatom fő forrásaként Martin Aigner és Günter M. Ziegler Bizonyítások a könyvből című könyvét használtam. Dolgozatom középpontjában az egyik talán legismertebb probléma áll, amelyet Sylvester mondott ki 1893-ban, az egyenesek helyzetével kapcsolatban. Erre a problémára - a Sylvester-Gallai-tételre - mutatok be különböző bizonyításokat, majd kimondom egy következményét, amit általánosan is megfogalmazok és kétféleképpen be is bizonyítom. A 3. fejezetben néhány gráfelméleti definíció bevezetése után ismertetem az Euler-formulát, amiből levezetek néhány összefüggést a gráfokra vonatkozóan. Ezek után bemutatom, hogyan alkalmazhatjuk az Euler-formulát a Sylvester-Gallai-tételnek és ennek egy "színes" változatának a bizonyításában, végül a rácssokszög területképletének igazolásához. Befejezésképpen pedig megvizsgálom, hogy egy teljes gráf legalább hány teljes részgráfra, valamint hány teljes páros részgráfra bontható fel.