MathLabs

第4题

设G是有k条边的连通图。证明可以把边标为 1,2,…,k1,2,\ldots,k,使得每个关联两条或更多边的顶点处,这些边标签的最大公因数为1。
第 1/4 步：利用连续标签互质
上一步下一步
gcd⁡(t,t+1)=1\gcd(t,t+1)=1
详细分析

关键观察是任意两个连续正整数的最大公因数为1。因此关联两条连续编号边的顶点自动满足条件,不受其他关联边影响。