Such a strange property

$P_G$ is the chromatic polynomial of $G$ , and it has the property that for any positive integer $n$ , $P_G(n)$ is precisely the number of ways to color $G$ using $n$ colors (so this is true for all positive integers, not only for up to $|V(G)|$ as described in the problem statement).

For a $k$ -strange graph, the chromatic polynomial can be derived pretty easily. First, observe that any $k$ -strange graph has exactly one cycle, which is of length $k$ ; deleting any edge in this cycle gives a tree. Thus, $P_G$ can be computed as follows. Consider any coloring of the cycle; then, starting from the cycle and moving outward, we color each of the remaining vertices. At any time, vertices not in this cycle have only 1 neighbor colored, and so given $n$ colors, we can color each vertex not in the cycle with $n-1$ remaining choices. Thus $P_G(n) = P_{C_k}(n) \cdot (n-1)^{2017-k}$ : the number of colorings for the cycle $C_k$ , multiplied by $(n-1)^{2017-k}$ for the remaining vertices. $P_{C_k}(n) = (n-1)^k + (-1)^k (n-1)$ is well known, or otherwise it can be derived easily by induction. This yields $P_G(n) = (n-1)^{2017} + (-1)^k (n-1)^{2018-k}$ .

We will now compute the number of odd coefficients in $P_G(n)$ . First, we take $P_G(n) \pmod{2} = (n+1)^{2017} + (n+1)^{2018-k}$ ; odd coefficients in the original $P_G$ translate to odd coefficients here, since we're taking modulo 2. Now, let $\nu_2(n)$ be the highest exponent of the power of 2 that divides $n$ . It's well-known that $\nu_2(n!) = \sum_{i=1}^\infty \left\lfloor \frac{n}{2^i} \right\rfloor$ , and by using this on the binomial coefficient $\binom{p}{q} = \frac{p!}{q! (p-q)!}$ , we obtain that $\binom{p}{q}$ is odd exactly when $\nu_2 \left( \binom{p}{q} \right) = 0$ , which in turn happens when $\nu_2(p!) = \nu_2(q!) + \nu_2((p-q)!)$ . Substituting the formula and simplifying, noting that $\left\lfloor \frac{p}{2^i} \right\rfloor \ge \left\lfloor \frac{q}{2^i} \right\rfloor + \left\lfloor \frac{p-q}{2^i} \right\rfloor$ for all $i$ , the condition $\nu_2(p!) = \nu_2(q!) + \nu_2((p-q)!)$ forces this inequality to be an equality for all $i$ . This happens exactly when, in the binary representation of $q$ , all set bits are also set in the binary representation of $p$ .

Note that $2017 = 11111100001_2$ ; it has 7 set bits and 4 unset bits. Suppose $2018-k$ has $a+b$ set bits, $a$ of them also set in 2017 and $b$ unset, and $c+d$ unset bits, $c$ of them set in 2017 and $d$ unset. For example, if $k = 100$ , then $2018-k = 1918 = 11101111110_2$ ; we have $a = 5, b = 4, c = 2, d = 0$ . Clearly we have the condition $a+c = 7, b+d = 4$ . Now consider the coefficient of $n^i$ in $(n+1)^{2017} + (n+1)^{2018-k}$ . We have the following, based on the binary representation of $i$ :

• If all set bits in $i$ are also set in 2017 and in $2018-k$ , then both $(n+1)^{2017}$ and $(n+1)^{2018-k}$ have odd coefficients for $n^i$ , and they add up to even.
• If all set bits in $i$ are also set in 2017, but not in $2018-k$ , then only $(n+1)^{2017}$ has odd coefficient for $n^i$ ; $(n+1)^{2018-k}$ has even coefficient, and they add up to odd. This can happen in $(2^c-1) \cdot 2^a$ ways: we must pick at least one set bit among the $c$ that are set in 2017 but not in $2018-k$ , and we can pick any combination of set bits among the $a$ that are set in 2017 and $2018-k$ .
• If all set bits in $i$ are set in $2018-k$ but not in 2017, the coefficient ends up odd. There are $(2^b-1) \cdot 2^a$ ways this can happen.
• If not all set bits in $i$ are also set in 2017, and neither in $2018-k$ , the coefficient ends up even.

The number of odd coefficients in $(n+1)^{2017} + (n+1)^{2018-k}$ is thus $2^{a+b} + 2^{a+c} - 2^{a+1}$ . We want to minimize this value. We know that $a+c = 7$ ; thus, to minimize this value, we want $a$ as large as possible and $b$ as small as possible. Of course, this would have been satisfied by $a = 7, b = 0, c = 0$ , but then $2018-k = 2017$ and so $k = 1$ , impossible. Thus we'll have to do with the second smallest: $a = 6, b = 0, c = 1$ . This means $2018-k$ has 6 of the 7 set bits in 2017. This cannot be the last bit, as that means $2018-k = 2017-1$ or $k = 2$ , also incorrect. But we can choose any of the other six bits: $2018-k = 2017-2^i$ for any choice of $i \in \{5, 6, 7, 8, 9, 10\}$ . This means the sum of all $k$ is simply $(2^5+1) + (2^6+1) + \ldots + (2^{10}+1) = \boxed{2022}$ .