Uluslararası Matematik Olimpiyatı 1991 Soru 4

[ERhan ERdoğan]

$G$ nin $k$ kenarlı bağlı bir çizge olduğunu varsayalım. Kenarları, her köşe iki veya daha çok kenara ait olacak ve bu kenarların etiketlerinin en büyük ortak böleni $1$ olacak şekilde,  $1,2,\dots, k$ sayıları ile etiketlendirmenin mümkün olduğunu kanıtlayınız.
$[$ Bir çizge, uçlar diye adlandırılan noktalar kümesi ile bu uçlardan bazı çiftleri birleştiren kenarlar kümesinden oluşur. Her $u,v$ uç çifti, en fazla bir kenara aittir. Her farklı $x,y$ uçları için, her $v_i,v_{i+1}$ ($0\leq i < m$) çifti $G$ nin bir kenarı tarafından birleştirilecek ve $x=v_0,v_1,v_2,\dots, v_m=y$ olacak şekilde bir uçlar dizisi varsa, $G$ çizgesi bağlıdır diyoruz.$]$