Bài 3

Vì $(n,1)\in G$, tính bắc cầu cấm $(1,n-1)$. Nếu có hơn $n-2$ cặp liên quan chỉ số $n$, thì cả $n-1$ cặp biên khả dĩ đều xuất hiện; bắt đầu từ $(n,1)$ và dùng tính bắc cầu sẽ buộc $(1,n)$, trái với cặp vòng bị cấm. Do đó $|G\setminus G'|\le n-2$.