Um grafo é um grafo euleriano se ele contém um tour euleriano.
Um tour euleriano (ou circuito euleriano) é uma trilha euleriana fechada, ou seja, que começa e termina no mesmo vértice.
Uma trilha euleriana em um grafo é um passeio que atravessa todas as arestas de passando por cada uma apenas uma vez.
Um grafo conexo tem um tour euleriano se e somente se ele não tem vértices de grau ímpar. Da mesma forma, um grafo conexo tem uma trilha euleriana se e somente se ele tem no máximo dois vértices de grau ímpar.