Question 51
A connected simple graph $G$ with maximum degree $d \gt 3$ is given. Suppose that
$$
x_d \geq x_{d-1} + 2x_{d-2} + \dots + (d-1)x_1,
$$
where $x_i$ is the number of vertices of degree $i$. Prove that there is a vertex of degree $d$ in $G$ such that after removing it the graph remains connected.
$$
x_d \geq x_{d-1} + 2x_{d-2} + \dots + (d-1)x_1,
$$
where $x_i$ is the number of vertices of degree $i$. Prove that there is a vertex of degree $d$ in $G$ such that after removing it the graph remains connected.