MathDB
Need help with Graph problem in space

Source: sourced from a training material, origin unkown

April 12, 2020
graph theory

Problem Statement

Let S be a set of n≥3n\geq 3 points in space. We color some line segments having two points in SS as their endpoints red, let rr be the number of edges colored red (color rr edges red). We know no two colored segmentes have the same length. Proof there is a path of red edges increasing in size of length at least ⌈2rn⌉\Bigg\lceil\frac{2r}{n}\Bigg\rceil.
Back to ProblemsView on AoPS