olymmath

IMO 1991 Problem 4

Suppose G is a connected graph with k edges. Prove that it is possible to label the edges 1, 2, ... , k in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is 1. [A graph is a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of edges belongs to at most one edge. The graph is connected if for each pair of distinct vertices x, y there is some sequence of vertices x = v0v_0, v1v_1, ... , vmv_m = y, such that each pair viv_i, vi+1v_{i+1} (0 ≤ i < m) is joined by an edge.]

Community text Kalva (prase.cz mirror). Quoted with source.

Solutions

No solution is on olymmath yet. Official and human solutions come first when they arrive. AI solutions come after them, with a label.

Add a solution

Similar problems

These problems have the most words in common with this statement.

Locator imo/1991/p4 · Tag AC6SBQPF90 · Edit this page on GitHub · Keys: j next, k previous