Definicje
Różni autorzy stosują bardzo odmienne sposoby definiowania i oznaczania elementów grafu.
Graf nieskierowany
Graf lub graf nieskierowany to uporządkowana para G := (V,E) gdzie:
- V jest niepustym zbiorem. Elementy tego zbioru nazywamy wierzchołkami,
- E jest rodziną dwuelementowych podzbiorów zbioru wierzchołków V, zwanych krawędziami:
.
Wierzchołki należące do krawędzi nazywane są jej końcami. Zazwyczaj V (i co za tym idzie E) są określane jako zbiory skończone. Jednak powyższa definicja tego nie wymaga i w praktyce rozważa się też czasami grafy o nieskończonej liczbie wierzchołków (wtedy liczba krawędzi może być skończona, lub nieskończona).
Graf skierowany
Graf skierowany lub inaczej digraf to uporządkowana para G := (V,A) gdzie:
- V jest zbiorem wierzchołków,
- A jest zbiorem uporządkowanych par różnych wierzchołków ze zbioru V, zwanych krawędziami skierowanymi, lub łukami:
.
Przyjmuje się, że krawędź e:=(x,y) jest skierowana z x do y, czyli wychodzi z x, a wchodzi do y.
Graf mieszany
Graf mieszany to uporządkowana trójka G:=(V,E,A) gdzie zbiory V,E,A są zdefiniowane jak wyżej, czyli może zawierać jednocześnie krawędzie skierowane i nieskierowane.
Warianty definicji
W wielu zastosowaniach tak zdefiniowane grafy nie są wystarczające i wprowadza się pewne modyfikacje.
Na przykład aby wprowadzić pętlę czyli krawędź, której oba końce są tym samym wierzchołkiem, w definicji grafu nieskierowanego należy dopuścić zbiory jednoelementowe {v} albo użyć dwuelementowego multizbioru {v,v}. W grafie skierowanym pętla jest naturalnie reprezentowana przez parę (v,v).
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 E, lub A jako multizbioru.
Przez zdefiniowanie funcji z V, E, lub A w pewnien zbiór X, można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatowych informacji. Etykiety liczbowe są często nazywane wagami. Dla grafów z wagami zbiór tworzący graf jest rozszerzony o funkcję 
taką, że dla każdej krawędzi 
, 
jest wagą danej krawędzi.
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 (zob. też "macierz sąsiedztwa" poniżej).
- Graf nieskierowany można też definiować jako trójkę 
, gdzie
*
jest zbiorem wierzchołków
*
zbiorem krawędzi
*
funkcją ze zbioru krawędzi w rodzinę jedno- i dwuelementowych podzbiorów zbioru wierzchołków – 
. Wówczas jeżeli 
jest krawędzią grafu to:
- kończy się ona wierzchołkami
, gdy 
- jest ona pętlą, gdy
, gdzie zbiory i są zdefiniowane analogicznie do grafów nieskierowanych a jest funkcją ze zbioru krawędzi w zbiór uporządkowanych par (kwadrat kartezjański, czyli iloczyn kartezjański zbioru ze sobą) wierzchołków – 
. Wówczas jeżeli jest krawędzią grafu 
to istnieją takie wierzchołki , że 
. W takim przypadku krawędź biegnie z do .
Graf geometryczny
Dla każdego grafu istnieje nieskończenie wiele przedstawiających go rysunków, czasami jednak rozważane są w przypadku grafów własności stricte geometryczne (współrzędne geometryczne wierzchołków, tylko proste krawędzie, "zmieszczenie się" w pewnej przestrzeni itp.). Grafy rozpatrywane jako figury w przestrzeni (w której są one "zanurzone" i która nadaje im cechy charakterystyczne dla danej przestrzeni) nazywa się grafami geometrycznymi.