MathLabs

第4题

设G是有k条边的连通图。证明可以把边标为 1,2,…,k1,2,\ldots,k,使得每个关联两条或更多边的顶点处,这些边标签的最大公因数为1。
第 3/4 步：处理起点
上一步下一步
gcd⁡{labels at A}=1ordeg⁡(A)=1\gcd\{\text{labels at }A\}=1\quad\text{or}\quad\deg(A)=1
详细分析

第一条路径的第一条边赋予标签1。因此起点A若关联至少两条边,其最大公因数为1;若只有一条边则无需条件。终点B要么是叶子,要么已是内部或先前处理过的安全顶点。