Given is a graph $G$ of $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
Source: St Petersburg 2022 10.7 (rephrased)
Tags: combinatorics, graph theory, algebra, Kvant
dgrozev
02.10.2022 17:25
So, the graph $G$ is a tree. Take any vertex $v_0$ and let $v_1,v_2,\dots,v_d$ be its neighbors. Denote $\Delta(v_0v_i)=\Delta_i:=w(v_0)-w(v_i)$ where by $w(v)$ we denote the weight of the vertex $v$. The given condition yields $$\Delta_1+\Delta_2+\dots+\Delta_d\le d$$which implies $$\Delta_i\le d+\sum_{j\ne i}|\Delta_j|\qquad(1)$$Let now $v_0$ be the vertex with $w(v_0)=0$. We take it as the root of the tree. It easily follows (starting from the leaves of the tree and using $(1)$) that for any edge $e=uv, u<v$ we have $$\Delta(e)\le \sum_{x>u}d(x)$$Let $y$ be any vertex of $G$ and $v_0v_1\dots v_i v_{i+1}=y$ be the path from $v_0$ to $y$. We have \begin{align*} |w(y)|\le \left|\sum_{j=0}^i\Delta(v_jv_{j+1})\right|&\le \sum_{j=0}^i\sum_{x>v_j}d(x)\\ &\le \sum_{j=0}^i \left(2|E(T(x_{j+1}))|+1\right)\\ &\le 2\big((n-1)+(n-2)+\dots+(n-i-1)\big)+(i+1)\\ &\le (n-1)n+n\\ &=n^2 \end{align*}where $T(x)$ denotes the subtree with root $x$. The equality is achieved when $G$ is a path of length $n$.
oVlad
08.03.2023 16:32
This is problem M2713 from Issue 8 of the Kvant Magazine, 2022. It was proposed by D. Fomin and A. Kirichenko.