MathDB
Non-existence of a special vertex implies bound for the longest path of a tree

Source: Bulgarian Spring Tournament 2023 11.4

March 25, 2023
combinatorics

Problem Statement

Given is a tree GG with 20232023 vertices. The longest path in the graph has length 2n2n. A vertex is called good if it has degree at most 66. Find the smallest possible value of nn if there doesn't exist a vertex having 66 good neighbors.
Back to ProblemsView on AoPS