MathDB

Given is a graph

G

n+1

vertices, which is constructed as follows: initially there is only one vertex

v

, and one a move we can add a vertex and connect it to exactly one among the previous vertices. The vertices have non-negative real weights such that

v

has weight

0

and each other vertex has a weight not exceeding the avarage weight of its neighbors, increased by

1

. Prove that no weight can exceed

n^2

Problem Statement