Each of the $29$ people attending a party wears one of three different types of hats. Call a person lucky if at least two of his friends wear different types of hats. Show that it is always possible to replace the hat of a person at this party with a hat of one of the other two types, in a way that the total number of lucky people is not reduced.
Problem
Source: 2022 Turkey JBMO TST P3
Tags: combinatorics
16.03.2022 00:30
02.08.2022 18:58
@hakN How do you obtain that $d_j(v) \geq 2$ for every $v$? We do indeed have $d_i(v) \leq 2$ and $d_i(v) + d_j(v) \geq 2$ but it is quite unclear how to show $d_j(v) \geq 2$. Also, the claim "$d_i(v) = 2$ only if $d_i(v) + d_j(v) = 2$" is correct but does not really fit with $d_j(v) \geq 2$ since if equality holds then the overall degree will be $4$ and not $2$. Any help please? UPDATE: Actually, "$d_i(v) = 2$ only if $d_i(v) + d_j(v) = 2$" need not be true if $H$ is a multigraph (and in fact we cannot really prove it is not such). Also, how do we know in general that $H$ even has edges?? In particular, you certainly cannot give lower bounds on degrees without having additional assumptions.
02.08.2022 21:40
Sorry for being unclear, here are the explanations: Throughout the solution, don't forget that $V(G) = V(H)$. $d(v)$ and $N(v)$ denotes the degree of $v$ and the set of neighbours of $v$ in graph $G$, not in $H$. So $d_j(v)+d_i(v)$ is not $d(v)$ necessarily. Also $H$ can be a multigraph. First, assume that $d_j(u)=0$ for some $u \in V(G)$. Then change $u$'s color with any arbitrary color different from $u$'s color. Assume that there is some lucky $v \in N(u)$ such that after this change, $v$ becomes unlucky. Then all the friends of $v$ other than $u$ has to have the new $u$'s color, but then we would have $u \to v$ in $H$, contradiction. So no lucky friend of $v$ becomes unlucky, thus the number of lucky people is not reduced, which contradicts our assumption. Similarly, if $d_j(v)=1$, since when changing $v$'s color, we have 2 color options, we have a similar contradiction. Thus, $d_j(u) \geq 2$ for all $u \in V(G)$. Now assume that $d_i(u) = 2$ and $d(u) \geq 3$ for some $u \in V(G)$. Let $v \to u$ and $w \to u$ be the incoming edges to $u$ in graph $H$. Then all neighbours of $u$ except $v$ must have the same color which is different from $v$'s color since $v \to u$. Similarly, all neighbours of $u$ except $w$ must have the same color which is different from $w$'s color. So, since $u$ has at least one more neighbour other than $v$ and $w$, all neighbours of $u$ have the same color, but this contradicts the fact that all neighbours of $u$ except $v$ having the same color which is different from $v$'s color. So $d_i(u) = 2$ implies that $d(u)=2$ since we assumed all degrees are at least two. Also it is clear that $d_i(u) \leq 2$ for all $u \in V(G)$. Now, $2 \cdot V(G) \geq \sum_{u \in V(G)} d_i(u) = \sum_{u \in V(G)} d_j(u) \geq 2 \cdot V(G)$, and for equality we must have $d(u)=2$ for all $u \in V(G)$.