Problem B. 5509. (January 2026)

B. 5509. Let $\displaystyle V=\{v_1,v_2,\ldots,v_n\}$ be the set of vertices of a graph on $\displaystyle n$ vertices, and let $\displaystyle d_i$ denote the degree of vertex $\displaystyle v_i$. We call function $\displaystyle f$ Verőcese, if it takes non-negative real values and for every edge $\displaystyle v_iv_j$ of the graph $\displaystyle f(v_i)+f(v_j)\geq d_i+d_j$ holds. Find the largest real number $\displaystyle \lambda$ such that for every $\displaystyle n$, every simple graph on $\displaystyle n$ vertices and every Verőcese function $\displaystyle f$ $\displaystyle f(v_1)+f(v_2)+\ldots+f(v_n)\geq\lambda(d_1+d_2+\ldots+d_n)$ holds true.

Proposed by Boldizsár Varga, Verőce

(6 pont)

Deadline expired on February 10, 2026.

Sorry, the solution is available only in Hungarian. Google translation

1. megoldás. Ha $\displaystyle n\ge2$, és a gráf egy csillaggráf, azaz például a $\displaystyle v_1$ csúcs – ez lesz csillag közepe – össze van kötve az összes többi csúccsal, azok között pedig nincs további él, akkor a fokszámok $\displaystyle d_1=n-1$ és $\displaystyle d_2=d_3=\ldots=d_n=1$, ezek összege $\displaystyle d_1+\ldots+d_n=2(n-1)$. Az $\displaystyle f(v_1)=n$, $\displaystyle f(v_2)=f(v_3)=\ldots=f(v_n)=0$ függvény eleget tesz a feltételnek, és $\displaystyle f(v_1)+\dots+f(v_n)=n$, tehát ebben az esetben

$\displaystyle f(v_1) + f(v_2) + \ldots + f(v_n) = \dfrac{n}{2n-2} (d_1 + d_2 + \ldots + d_n). $

$\displaystyle (1) $

Ez a példa mutatja, hogy

$\displaystyle \lambda\le\dfrac{n}{2n-2}=\dfrac12+\frac{1}{2(n-1)}. $

Az $\displaystyle n\to\infty$ határátmenetből azt kapjuk, hogy $\displaystyle \lambda\le\dfrac12$.

Megmutatjuk, hogy a $\displaystyle \lambda=\dfrac12$ számra igaz a feltétel: tetszőleges $\displaystyle n$ csúcsú egyszerű gráf és verőcei függvény esetén

$\displaystyle f(v_1) + f(v_2) + \ldots + f(v_n) \ge \dfrac12(d_1 + d_2 + \ldots + d_n). $

$\displaystyle (2) $

Legyen a gráf éleinek (a megfelelő $\displaystyle \{i,j\}$ indexpárok) halmaza $\displaystyle E$; vegyük észre, hogy a jobb oldalon éppen gráf éleinek száma áll: $\displaystyle \dfrac12(d_1 + d_2 + \ldots + d_n)=|E|$.

Színezzük pirosra azokat a $\displaystyle v_i$ csúcsokat, amelyekre $\displaystyle f(v_i)\ge d_i$. Vegyük észre, hogy bármely két szomszédos $\displaystyle v_i$ és $\displaystyle v_j$ csúcs közül legalább az egyik piros, mert a feltétel szerint $\displaystyle f(v_i)+f(v_j)\ge d_i+d_j$, és emiatt $\displaystyle f(v_i)\ge d_i$ és $\displaystyle f(v_j)\ge d_j$ közül legalább az egyik teljesül.

Minden piros csúcsra jelöljük meg a belőle kiinduló éleket (egy élt akár mindkét végénél is megjelölhetünk), ezzel minden élt legalább egyszer megjelölünk. Másrészt minden piros $\displaystyle v_i$ csúcsnál legfeljebb $\displaystyle d_i$ élt jelölünk meg, ezért

$\displaystyle \sum_{i=1}^n f(v_i) \ge \sum_{\text{\(\displaystyle v_i$ piros}} f(v_i) \ge \sum_{\text{$\displaystyle v_i$ piros}} d_i \ge |E| = \dfrac12\sum_{i=1}^n d_i. \)

Ezzel megmutattuk, hogy $\displaystyle \lambda=\dfrac12$ a legnagyobb szám amely minden egyszerű gráf és verőcei függvény esetén teljesíti a feltételt.

2. megoldás. Az 1. megoldáshoz hasonlóan látjuk, hogy $\displaystyle n\ge$ esetén $\displaystyle \lambda\le\dfrac{n}{2(n-1)}$.

Megmutatjuk, hogy tetszőleges $\displaystyle n\ge2$ csúcsú egyszerű gráf és verőcei $\displaystyle f$ függvény esetén

$\displaystyle \sum_{i=1}^n f(v_i) \ge \dfrac{n}{2(n-1)}\sum_{i=1}^n d_i. $

A becslést úgy kapjuk, hogy a gráf összes élére összeadjuk az $\displaystyle \dfrac{f(v_i)+f(v_j)}{d_i+d_j}\ge1$ egyenlőtlenséget. Az éleket mindkét irányban számolva,

$$\begin{gather*} \sum_{i=1}^n d_i =2|E| =\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}1 \le\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_i)+f(v_j)}{d_i+d_j} =\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_i)}{d_i+d_j}+\sum_{\substack{1\le i,j\le n\\\{i,j\}\in E}}\dfrac{f(v_j)}{d_i+d_j} =\\ =2\sum_{i=1}^n \left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac{f(v_i)}{d_i+d_j}\right) =2\sum_{i=1}^n f(v_i)\left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac1{d_i+d_j}\right) \le2\sum_{i=1}^n f(v_i)\left(\sum_{\substack{1\le j\le n\\\{i,j\}\in E}} \dfrac1{d_i+1}\right) =\\ =2\sum_{i=1}^n f(v_i)\dfrac{d_i}{d_i+1} \le 2\sum_{i=1}^n f(v_i)\dfrac{n-1}{n} =\dfrac{2(n-1)}{n}\sum_{i=1}^n f(v_i), \end{gather*}$$

tehát

$\displaystyle \sum_{i=1}^n f(v_i) \ge \dfrac{n}{2(n-1)}\sum_{i=1}^n d_i. $

Statistics:

24 students sent a solution.

6 points: Ali Richárd, Bodor Ádám, Bolla Donát Andor, Ercse Ferenc, Gál Mózes, Hajba Milán, Kun Zsófia, Miszori Márton, Pázmándi József Áron, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Tóth László Pál.

5 points: Balla Ignác , Görömbey Tamás.

2 points: 1 student.

1 point: 4 students.

0 point: 3 students.

Unfair, not evaluated: 1 solutions.

Problems in Mathematics of KöMaL, January 2026

24 students sent a solution.
6 points:	Ali Richárd, Bodor Ádám, Bolla Donát Andor, Ercse Ferenc, Gál Mózes, Hajba Milán, Kun Zsófia, Miszori Márton, Pázmándi József Áron, Rajtik Sándor Barnabás, Sajter Klaus, Sánta Gergely Péter, Tóth László Pál.
5 points:	Balla Ignác , Görömbey Tamás.
2 points:	1 student.
1 point:	4 students.
0 point:	3 students.
Unfair, not evaluated:	1 solutions.

Already signed up?
New to KöMaL?