Az 1. fejezet első részét a gráfelméleti alapfogalmak bevezetésének szenteltem. Ennek elsődleges célja, hogy a témában kevésbé járatos olvasó számára is egyszerűbbé váljon az ezt követő, esetleg nehezebbnek tűnő fejezetek megértése is. A fejezet második része főként a 3. fejezetben előforduló fogalmak megértését segíti, de megemlítjük a híres P=NP problémát is. A 2. fejezet három részre tagolódik. Az első részben a páros gráfokkal foglalkozom. A páros gráfok olyan gráfok, amelyeknél a csúcspontok két diszjunkt halmaz uniójára bonthatók úgy, hogy az összes élre teljesül, hogy az egyik végpont az egyik halmazban, míg a másik végpont a másik halmazban van. A fejezet második része e páros gráfok párosításaival foglalkozik. Párosítás nem csak páros gráfok esetén létezhet, hanem általános gráfok esetén is. Ennek tárgyalására hivatott a harmadik alfejezet. Ebben a részben két híres magyar matematikus Kőnig Dénes és Egerváry Jenő tiszteletére magyar-módszernek elnevezett eljárás ismertetése következik. 3. fejezetben érünk el, diplomamunkám legfontosabb részéhez, amelyben említést teszek gráfok kiterjeszthetőségéről is. Ebben a fejezetben vizsgálom az úgynevezett karom-mentes gráfok BM-kiterjeszthetőségéhez szükséges és elegendő feltételeket. Bemutatom még az NP illetve co-NP problémákat is, ahol NP probléma alatt olyan problémát értünk, amelynek megoldására létezik olyan algoritmus amely polinomiális idő alatt megoldja azt. Végül pár szót ejtek néhány további, ebben a témában vizsgálatra érdemes kérdésekről is.