drogi. Droga – wyznaczona przez krawędzie trasa, polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziach. Jeżeli przez oznaczy się -tą krawędź grafu, to droga może być jednoznacznie zapisana jako . Droga prosta – droga niezawierająca dwóch tych samych krawędzi. Długość drogi/ścieżki – liczba krawędzi/wierzchołków, tworzących daną drogę/ścieżkę. Droga acykliczna – droga, niezawierająca cyklu. Drzewo spinające grafu – spójny, acykliczny podgraf danego grafu, zawierający wszystkie jego wierzchołki. Gęstość grafu – stosunek liczby krawędzi do największej możliwej liczby krawędzi. Używa się również określeń: graf gęsty, jeżeli ma on dużo krawędzi w stosunku do liczby wierzchołków, i podobnie graf rzadki, jeżeli ma on mało krawędzi w stosunku do liczby wierzchołków, przy czym znaczenie słów mało i dużo może zależeć od kontekstu. Klika – podzbiór wierzchołków danego grafu wraz z krawędziami je łączącymi, takich, że każde dwa wierzchołki tego podzbioru są sąsiadami (czyli podgraf pełny). Kolorowanie grafu – nadanie każdemu wierzchołkowi koloru tak, by żadne sąsiadujące ze sobą wierzchołki nie były pokolorowane tym samym kolorem. Krawędzie sąsiednie – krawędzie kończące się w jednym wierzchołku. W przypadku grafów skierowanych zazwyczaj wymagana jest zgodność kierunków krawędzi, tj. dwie krawędzie są sąsiednie, jeżeli odpowiednio kończą się i zaczynają w tym samym wierzchołku.