Xem đồ thị Euler và Hamilton. Trước hết, cần biết đường đi (trail) trong đồ thị. Giả sử đồ thị:
Trail là đường đi là chuỗi cạnh (v1,v2), (v2,v3), …, (vk-1,vk) trong đó các đỉnh có thể trùng nhưng cạnh đều khác nhau. Ví dụ trail: {(B,A), (A,C), (C,D), (D,A), (A,F)}. Đây là trail nhưng không phải đường đơn (simple path) vì A xuất hiện 2 lần. Nếu đỉnh đầu và cuối trùng nhau, đó là closed trail.
Eulerian Trail
Eulerian Trail trong G(V,E) là trail đi qua mỗi cạnh đúng một lần. Nếu G có closed Eulerian Trail, G gọi là Eulerian Graph. Tức là từ một đỉnh, đi qua mọi cạnh đúng một lần và quay về đỉnh xuất phát. Euler chứng minh: G là Eulerian graph当且仅当 mọi đỉnh đều có bậc chẵn.
Chu trình Hamilton
Chu trình gọi là Hamilton nếu đi qua mọi đỉnh của G. Có nhiều định lý cho điều kiện đủ để đồ thị Hamilton, nhưng bài toán xác định đồ thị Hamilton là NP-Complete.