Problem

Source: Iranian TST 2021, first exam day 1, problem 2

Tags: combinatorics, graph theory



In the simple and connected graph $G$ let $x_i$ be the number of vertices with degree $i$. Let $d>3$ be the biggest degree in the graph $G$. Prove that if : $$x_d \ge x_{d-1} + 2x_{d-2}+... +(d-1)x_1$$Then there exists a vertex with degree $d$ such that after removing that vertex the graph $G$ is still connected. Proposed by Ali Mirzaie