设 $G$ 是一个有 $k$ 条棱的连通图，求证：可以将 $G$ 的棱标号为 $1,2,\cdots,k$ 使得在每一个属于两条或更多棱的顶点，过该顶点各条棱的标号数的最大公因子是 $1$．
（美国）
（美国）
【难度】
【出处】
1991年第32届IMO试题
【标注】
【答案】
略
【解析】
由 $G$ 的连通性可知，$G$ 的每一个顶点的度至少为 $1$．任取 $G$ 的一个顶点 $v_0$，从 $v_0$ 出发沿 $G$ 中的棱行走，每条棱至少能通过一次，但每个顶点可以通过多次，设通过 $l_1$ 条棱后不可能再继续前进，依次通过的顶点不妨设为 $v_0,v_1,\cdots,v_{l_1}$（其中的 $0\leqslant i<j\leqslant l_1$，$v_i$ 与 $v_j$ 可能是同一个顶点），将已通过的棱依次标号为 $1,2,\cdots,l_1$，显然，$1,\leqslant l_1\leqslant k$，且除去顶点 $v_0$ 外，其余任一顶点，若从它出发有两条或更多条棱被标号，则这些标号数必有两个是相邻的正整数．
如果 $l_1=k$，那么所有的棱均已被标号，否则 $1\leqslant l_1<k$．由 $G$ 的连通性可知，存在一顶点，它或者是 $v_0$，或者从它出发至少有两条棱已经被标过号，从该顶点出发的棱中还有尚未标过号的．我们从这一项点出发按上述规则沿尚未标过号的棱行走并从 $l_1+1$ 开始依次标号，直到不可能继续前进为止，设又标了 $l_2$ 条棱，则 $1\leqslant l_2\leqslant k-l_1$．由于总共只有 $k$ 条棱，用这种方法可以将 $G$ 中的所有棱标号为 $1,2,\cdots,k$．
对于 $G$ 中的任一顶点 $v$，设从 $v$ 出发至少有两条棱，若 $v=v_0$，由于从 $v_0$ 出发有一条棱标号为 $1$，从而过该点各棱的标号数的最大公因子为 $1$；若 $v\ne v_0$，则由上述的标号方法知，过顶点 $v$ 必有两条棱的标号数为相邻的正整数，它们互质，所以，过该点的各条棱的标号数的最大公因子为 $1$．
如果 $l_1=k$，那么所有的棱均已被标号，否则 $1\leqslant l_1<k$．由 $G$ 的连通性可知，存在一顶点，它或者是 $v_0$，或者从它出发至少有两条棱已经被标过号，从该顶点出发的棱中还有尚未标过号的．我们从这一项点出发按上述规则沿尚未标过号的棱行走并从 $l_1+1$ 开始依次标号，直到不可能继续前进为止，设又标了 $l_2$ 条棱，则 $1\leqslant l_2\leqslant k-l_1$．由于总共只有 $k$ 条棱，用这种方法可以将 $G$ 中的所有棱标号为 $1,2,\cdots,k$．
对于 $G$ 中的任一顶点 $v$，设从 $v$ 出发至少有两条棱，若 $v=v_0$，由于从 $v_0$ 出发有一条棱标号为 $1$，从而过该点各棱的标号数的最大公因子为 $1$；若 $v\ne v_0$，则由上述的标号方法知，过顶点 $v$ 必有两条棱的标号数为相邻的正整数，它们互质，所以，过该点的各条棱的标号数的最大公因子为 $1$．
答案
解析
备注
