MathDB

Let

n\geq 2

be a positive integer. We call a vertex every point in the coordinate plane, whose

x

and

y

coordinates both are from the set

\{1,2,3,...,n\}

. We call a segment between two vertices an edge, if its length if

1

. We've colored some edges red, such that between any two vertices, there is a unique path of red edges (a path may contain each edge at most once). The red edge

f

is vital for an edge

e

, if the path of red edges connecting the two endpoints of

e

contain

f

. Prove that there is a red edge, such that it is vital for at least

n

edges.

Problem Statement