Ein ungerichteter Graph auf einer Menge ${\displaystyle {}V}$ (die die Eckpunktmenge des Graphen heißt) besteht aus einer gewissen Auswahl an zweielementigen Teilmengen (die die Kantenmenge des Graphen heißt) von ${\displaystyle {}V}$.