Alice, who works for the Graph County Electric Works, is commissioned to wire the newly erected utility poles in $k$ days. Each day she either chooses a pole and runs wires from it to as many poles as she wishes, or chooses at most $17$ pairs of poles and runs wires between each pair. Bob, who works for the Graph County Paint Works, claims that, no matter how many poles there are and how Alice connects them, all the poles can be painted using not more than $2009$ colors in such a way that no pair of poles connected by a wire is the same color. Determine the greatest value of $k$ for which Bob's claim is valid.
Problem
Source:
Tags: combinatorics proposed, combinatorics
crazyfehmy
10.09.2010 19:43
Here is the official solution. Let $G=\cup_{i=1}^{k} G_i$ be a graph that can be vertex-colored using not more than $2009$ colors where each $G_i$ is either a star or $e(G_i) \leq 17$ for $1 \leq i \leq k.$ We want to find the maximum possible value of $k.$ Suppose that $G_i$ is a star for $1 \leq i \leq j,$ and $G_i$ satisfies $e(G_i) \leq 17$ for $j+1 \leq i \leq k$ where $0\leq j \leq k.$ If at least $j+10$ colors are needed to color $\cup_{i=1}^{j}G_i,$ then we must have $\dbinom{j+10}{2} \leq 17j$ and since $\left(j-\frac{15}{2}\right)^2+\frac{135}{4} \leq 0,$ this gives a contradiction. Hence it is possible to color $\cup_{i=1}^{j}G_i$ using at most $j+9$ colors. Since we might need at most one more color every time we add a star, we conclude that $G$ can be colored using not more than $k+9$ colors. On the other hand, if $k \geq 9,$ there is a case when $k+9$ is needed: We use $9 \; G_i$s to form a $C_{18}$ and then use $k-9$ stars to complete this to a $C_{k+9}.$ We conclude that the greatest value of $k$ for which $2009$ colors suffice is $2000.$
JSparrow
03.03.2019 21:04
Let the poles be vertices of a graph, and wires running between poles edges. Now, note that the smallest graph (in terms of number of vertices) that can't be colored with 2009 colors is $K_{2010}$, since all graphs with less than $2010$ vertices can clearly be colored with $2009$ colors (each vertex a distinct color) and a $K_{2010}$ missing a few edges could have 1 pair of nonadjacent vertices with the same color and each other vertex a different color. Thus, our maximum $k$ is $m-1$, where $m$ is the minimum number of moves Alice needs to construct a $K_{2010}$.
Let us restrict Alice to a subset of vertices, $\{V_1,V_2,...V_{2010} \}$. We need to choose which of Alice's moves she should make on each day to maximize the number of edges constructed per day. Let's define Operation 1 as "choosing a vertex and connecting it to all other vertices" and Operation 2 as "matching $17$ pairs of vertices". Clearly, if the $K_{2010}$ is missing more than $17$ edges, than Operation 1 would be more efficient, while otherwise Operation 2 would be more efficient. So, at maximal efficiency, Alice would perform Operation 1 on Day $x$ to construct $2010-x$ edges, for each integer $1 \leq x \leq 1993$. This leaves us with ${16 \choose 2}$, or $8 \cdot 17$, edges to construct using Operation 2. Clearly, this takes $8$ more days, so $m = 1993 + 8 = 2001$ and $k = 2001-1 = \boxed{2010}$.