1. Khái niệm đường đi Euler, Định lí Euler 2. Đường đi Hamilton, Nhận biết đương fđi Hamilton; định lí Ore, Dirac

1. Đường đi Euler: Đường đi Euler trong một đồ thị là một đường đi khép kín đi qua tất cả các cạnh của đồ thị đó. Một đồ thị có chứa đường đi Euler khi và chỉ khi đồ thị đó liên thông và tất cả các đỉnh của nó đều có bậc chẵn. Định lý Euler: Một đồ thị có chứa đường đi Euler khi và chỉ khi đồ thị đó liên thông và có tối đa 2 đỉnh bất kỳ có bậc lẻ. 2. Đường đi Hamilton: Đường đi Hamilton trong một đồ thị là một đường đi khép kín đi qua tất cả các đỉnh của đồ thị đó. Nhận biết đường đi Hamilton: - Đối với đồ thị vô hướng, nếu đồ thị là liên thông và có n đỉnh thì nó có đường đi Hamilton. - Đối với đồ thị có hướng, nếu đồ thị là liên thông mạnh thì nó có đường đi Hamilton. Định lý Ore: Nếu G là một đồ thị vô hướng với n đỉnh (n ≥ 3) sao cho bậc của mỗi cặp đỉnh không kề nhau u, v thỏa mãn deg(u) + deg(v) ≥ n thì G có đường đi Hamilton. Định lý Dirac: Nếu G là một đồ thị vô hướng với n đỉnh (n ≥ 3) sao cho bậc của mỗi đỉnh u thỏa mãn deg(u) ≥ n/2 thì G có đường đi Hamilton. Các định lý này giúp chúng ta nhận biết và xác định xem một đồ thị có chứa đường đi Euler hay đường đi Hamilton hay không.