IMO 1991 Problem 4
- Day 2
- Difficulty band 6
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 = , , ... , = y, such that each pair , (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.
Similar problems
These problems have the most words in common with this statement.