Graf nieskierowany thumb|Multigraf półeulerowski Obecnie grafy, które rozważał Euler nazywane są grafami nieskierowanymi. Liczba krawędzi stykających się z danym wierzchołkiem nazywana jest jego stopniem. Jeżeli wszystkie wierzchołki grafu nieskierowanego mają stopień parzysty, a graf jest spójny, to znaczy, że da się skonstruować zamkniętą ścieżkę Eulera nazywaną cyklem Eulera. Jeżeli najwyżej dwa wierzchołki mają nieparzysty stopień, to możliwe jest zbudowanie tylko takiej ścieżki Eulera, która nie jest zamknięta. Graf zawierający cykl Eulera jest nazywany grafem eulerowskim, a graf posiadający jedynie ścieżkę Eulera nazywany jest półeulerowskim (pseudoeulerowskim). Inna definicja określa nieskierowany graf eulerowski jako graf spójny, dla którego wszystkie wierzchołki są stopnia parzystego.
Graf skierowany Graf skierowany różni się tym, od nieskierowanego, że ruch może odbywać się tylko w kierunkach wyznaczonych przez krawędzie. Poruszanie się „pod prąd” jest zabronione. Każdy wierzchołek posiada pewną liczbę krawędzi wejściowych nazywaną stopniem wchodzącym. Analogicznie ilość krawędzi wychodzących to stopień wychodzący.