Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh cùng bậc.

Lời giải:

Đồ thị Hình 2.42 chỉ có hai đỉnh bậc lẻ là D và E nên ta có thể tìm được một đường đi Euler từ D đến E (đường đi này đi qua mỗi cạnh đúng một lần).

Một đường đi Euler từ D đến E là DBACDEBCE và tổng độ dài của nó là

2 + 4 + 4 + 2 + 6 + 3 + 5 + 1 = 27.

Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ E đến D theo thuật toán gắn nhãn vĩnh viễn.

Đường đi ngắn nhất từ E đến D là ECD và có độ dài là 1 + 2 = 3.

Vậy một chu trình cần tìm là DBACDEBCECD và có độ dài là 27 + 3 = 30.