Bài 4

Cho G là một đồ thị liên thông có k cạnh. Chứng minh có thể gán nhãn các cạnh bằng

1,2,\ldots,k

sao cho tại mỗi đỉnh thuộc từ hai cạnh trở lên, ước chung lớn nhất của các số gán cho những cạnh đó bằng 1.

Bước 2 trên 4: Gán nhãn liên tiếp cho mỗi đường đi chưa gán nhãn cực đại

Bước trước Bước tiếp

e_1,e_2,\ldots,e_s\quad\mapsto\quad q,q+1,\ldots,q+s-1

Phân tích chi tiết

Bắt đầu tại đỉnh A và đi theo một đường qua các cạnh chưa gán nhãn cho tới khi tới đỉnh B không còn cạnh chưa gán nhãn. Gán cho các cạnh vừa đi qua các nhãn chưa dùng liên tiếp tiếp theo. Mọi đỉnh bên trong đường đi kề hai nhãn liên tiếp nên an toàn.