MathDB
Connected graphs on a Tst

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

May 17, 2021
combinatoricsgraph theory

Problem Statement

In the simple and connected graph GG let xix_i be the number of vertices with degree ii. Let d>3d>3 be the biggest degree in the graph GG. Prove that if : xd≥xd−1+2xd−2+...+(d−1)x1x_d \ge x_{d-1} + 2x_{d-2}+... +(d-1)x_1 Then there exists a vertex with degree dd such that after removing that vertex the graph GG is still connected.
Proposed by Ali Mirzaie
Back to ProblemsView on AoPS