Das als Graphentheorie bekannte Gebiet ist ein Zweig der Mathematik, der sich sowohl in praktischer als auch in theoretischer Hinsicht eines speziellen Bündnisses mit der Informatik erfreut. Einmal können die Sprache, die Verfahren und die Sätze der Graphentheorie auf so verschiedene Systeme wie Datenstrukturen und Ableitungsbäume angewandt werden. Zweitens ist die Graphentheorie selbst reich an Problemen, die unsere Fähigkeit herausfordern, sie mit dem Computer zu lösen. Tatsächlich scheint es nur für wenige graphentheoretische Probleme Algorithmen zu geben, die sie in polynomialer Laufzeit lösen. Viele der ersten Aufgaben, für die gezeigt wurde, daß sie NP-vollständig sind, waren Probleme der Graphentheorie.