11.4

Part of 2023 Bulgarian Spring Mathematical Competition

Problems(1)

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

Source: Bulgarian Spring Tournament 2023 11.4

Given is a tree

G

2023

vertices. The longest path in the graph has length

2n

. A vertex is called good if it has degree at most

6

. Find the smallest possible value of

n

if there doesn't exist a vertex having

6

good neighbors.