MathDB
Tree inequality graph theory

Source: Turkey TST 2022 P9 Day 3

March 13, 2022
combinatoricscombinatorics proposedinequalitiesgraph theory

Problem Statement

In every acyclic graph with 2022 vertices we can choose kk of the vertices such that every chosen vertex has at most 2 edges to chosen vertices. Find the maximum possible value of kk.