MathDB
assignment of vertices and edges?

Source: IMO 2022 Malaysian Training Camp 1

February 26, 2022
combinatorics

Problem Statement

Given a graph GG, consider the following two quantities,
∙\bullet Assign to each vertex a number in {0,1,2}\{0,1,2\} such that for every edge e=uve=uv, the numbers assigned to uu and vv have sum at least 22. Let A(G)A(G) be the minimum possible sum of the numbers written to each vertex satisfying this condition.
∙\bullet Assign to each edge a number in {0,1,2}\{0,1,2\} such that for every vertex vv, the sum of numbers on all edges containing vv is at most 22. Let B(G)B(G) be the maximum possible sum of the numbers written to each edge satisfying this condition.
Prove that A(G)=B(G)A(G)=B(G) for every graph GG.
[Note: This question is not original]
[Extra: Show that this statement is still true if we replace 22 to nn, if and only if nn is even (where we replace {0,1,2}\{0,1,2\} to {0,1,⋯ ,n}\{0,1,\cdots, n\})]
Back to ProblemsView on AoPS