Problem

Source: IMO 2022 Malaysian Training Camp 1

Tags: combinatorics



Given a graph $G$, consider the following two quantities, $\bullet$ Assign to each vertex a number in $\{0,1,2\}$ such that for every edge $e=uv$, the numbers assigned to $u$ and $v$ have sum at least $2$. Let $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\}$ such that for every vertex $v$, the sum of numbers on all edges containing $v$ is at most $2$. Let $B(G)$ be the maximum possible sum of the numbers written to each edge satisfying this condition. Prove that $A(G)=B(G)$ for every graph $G$. [Note: This question is not original] [Extra: Show that this statement is still true if we replace $2$ to $n$, if and only if $n$ is even (where we replace $\{0,1,2\}$ to $\{0,1,\cdots, n\}$)]