MathDB
Connected spanning subgraphs map to points on a line

Source: Miklós Schweitzer 2016, Problem 2

November 2, 2016
graph theorycombinatoricsMiklos Schweitzercontests

Problem Statement

Let K=(V,E)K=(V,E) be a finite, simple, complete graph. Let dd be a positive integer. Let ϕ:E→Rd\phi:E\to \mathbb{R}^d be a map from the edge set to Euclidean space, such that the preimage of any point in the range defines a connected graph on the entire vertex set VV, and the points assigned to the edges of any triangle in KK are collinear. Show that the range of ϕ\phi is contained in a line.
Back to ProblemsView on AoPS