So wie endliche Graphen an verschiedenen Stellen der endlichen Mathematik auftreten, trifft man in der unendlichen Mathematik oft auf unendliche Graphen. Im Unendlichen wird eine befriedigende Graphentheorie jedoch durch pathologische Beispiele erschwert, die man zum Beispiel mit Hilfe des Auswahlaxioms konstruieren kann. Die in der Mathematik tatsächlich auftretenden unendlichen Graphen sind jedoch typischer Weise in der einen oder anderen Form definierbar. Definierbare Graphen lassen sich mit Methoden der deskriptiven Mengenlehre untersuchen. Es zeigt sich, dass man von der Definition eines Graphen auf seine strukturellen Eigenschaften schließen kann.