Czasami potrzebna jest możliwość połączenia dwóch wierzchołków przy pomocy więcej niż jednej krawędzi (w przypadku grafu skierowanego chodzi o łuki o takim samym zwrocie). Graf, który na to pozwala, nazywany jest multigrafem. Uzyskuje się go np. przez zdefiniowanie lub jako multizbioru.
Przykłady odmiennych sposobów definiowania grafu Graf może być też określony jako niepusty zbiór wierzchołków i dana na nim relacja binarna taka, że dla dowolnych wierzchołków i zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca i . Dla grafów nieskierowanych relacja ta jest symetryczna.
Graf nieskierowany można też definiować jako trójkę gdzie jest niepustym zbiorem, którego elementy nazywają się wierzchołkami, jest rodziną dwuelementowych podzbiorów zbioru wierzchołków zwanych krawędziami: a jest funkcją ze zbioru w zbiór wszystkich podzbiorów jedno- lub dwuelementowych zbioru Wówczas jeżeli jest krawędzią grafu, to kończy się ona wierzchołkami gdy i jest pętlą wierzchołka gdy