第4题

设G是有k条边的连通图。证明可以把边标为

1,2,\ldots,k

,使得每个关联两条或更多边的顶点处,这些边标签的最大公因数为1。

第 2/4 步：给每条极大未编号路径连续编号

e_1,e_2,\ldots,e_s\quad\mapsto\quad q,q+1,\ldots,q+s-1

详细分析

从顶点A开始,沿未编号边走到没有未编号边的端点B。给走过的边赋予接下来连续的未用标签。路径内部的每个顶点关联两个连续标签,因而满足条件。