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\}$)]
Problem
Source: IMO 2022 Malaysian Training Camp 1
Tags: combinatorics
navi_09220114
29.03.2022 06:45
Any ideas?
Sross314
29.03.2022 07:08
Assume G is an integer such 0 <= G <=4 for ease, if G is not an integer, A(G) = A(ceiling(G)), B(G) = B(floor(G)). Note that A(G) = B(4-G), by which is true by taking u' = 2-u for every vertex u of G.
It is equivalent to show A(G) = A(4-G) is true. How can we do this? Click to reveal hidden textUse same method again by subbing
Its easy to prove that this is true for even n by just using the same methods, none of them depended on n being 2.
For odd n, our goal is to find a general counterexample. (Haven't done this at time of writing yet)
navi_09220114
30.03.2022 22:18
I am confused, what do you mean by B(4-G)? in the question G is a graph and A(G) is a maximum over all possible graphs G
navi_09220114
18.07.2022 16:13
Any ideas?