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 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 1 trên 4: Dùng tính nguyên tố cùng nhau của hai nhãn liên tiếp
Phân tích chi tiết
Nhận xét then chốt là hai số nguyên dương liên tiếp luôn có ước chung lớn nhất bằng 1. Vì vậy một đỉnh kề hai cạnh mang nhãn liên tiếp tự động thỏa điều kiện, bất kể các cạnh khác kề với nó.