For a graph $G$ on $n$ vertices, let $P_G(x)$ be the unique polynomial of degree at most $n$ such that for each $i=0,1,2,\dots,n$, $P_G (i)$ equals the number of ways to color the vertices of the graph $G$ with $i$ distinct colors such that no two vertices connected by an edge have the same color. For each integer $3\le k \le 2017$, define a $k$-[i]tasty[/i] graph to be a connected graph on $2017$ vertices with $2017$ edges and a cycle of length $k$. Let the [i]tastiness[/i] of a $k$-tasty graph $G$ be the number of coefficients in $P_G(x)$ that are odd integers, and let $t$ be the minimal tastiness over all $k$-tasty graphs with $3\le k \le 2017$. Determine the sum of all integers $b$ between $3$ and $2017$ inclusive for which there exists a $b$-tasty graph with tastiness $t$.

[i]Proposed by Vincent Huang[/i]
1. Recognize that \( P_G(x) \) is the chromatic polynomial \( P(G, x) \). The chromatic polynomial \( P(G, x) \) of a graph \( G \) counts the number of ways to color the vertices of \( G \) with \( x \) colors such that no two adjacent vertices share the same color.
2. Use the well-known fact that for an edge \( uv \in E(G) \), the chromatic polynomial satisfies the relation:
   \[
   P(G, x) = P(G - uv, x) - P(G/uv, x)
   \]
   where \( G - uv \) is the graph obtained by removing the edge \( uv \) and \( G/uv \) is the graph obtained by contracting the edge \( uv \).
3. Let \( T_{n, k} \) be a \( k \)-tasty graph on \( n \) vertices. Note that \( T_{n, 2} \) is a tree \( T_n \), with the well-known chromatic polynomial:
   \[
   P(T_n, x) = x(x-1)^{n-1}
   \]
4. Pick an edge in the cycle of \( T_{n, k} \) and use the above identity. Removing the edge produces a tree, and contracting the edge produces a \( T_{n-1, k-1} \) graph. Thus:
   \[
   P(T_{n, k}, x) = P(T_n, x) - P(T_{n-1, k-1}, x)
   \]
5. Recurse this relation:
   \[
   P(T_{n, k}, x) = P(T_n, x) - P(T_{n-1}, x) + \cdots + (-1)^{k-2}P(T_{n-(k-2), k-(k-2)}, x)
   \]
   which simplifies to:
   \[
   P(T_{n, k}, x) = x(x-1)^{n-1} - x(x-1)^{n-2} + \cdots + (-1)^{k-2} x(x-1)^{n-k+2}
   \]
6. Work in \( \mathbb{F}_2 \) (the field with two elements). In \( \mathbb{F}_2 \), we can ignore negative signs and the factor of \( x \) multiplied over everything since that doesn’t affect the number of odd coefficients:
   \[
   (x-1)^{n-1} + (x-1)^{n-2} + \cdots + (x-1)^{n-k+2}
   \]
7. Factor out \( (x-1)^{n-k+2} \):
   \[
   (x-1)^{n-k+2} \left((x-1)^{k-3} + (x-1)^{k-4} + \cdots + 1\right)
   \]
8. Recognize the geometric series and simplify:
   \[
   (x-1)^{n-k+2} \left(\frac{(x-1)^{k-2} - 1}{x-2} \right)
   \]
9. In \( \mathbb{F}_2 \), \( x-2 \) is just \( x \), and we can ignore dividing by \( x \) since that doesn’t affect the count:
   \[
   (x-1)^{n-k+2}\left((x-1)^{k-2} - 1\right) = (x-1)^n - (x-1)^{n-k+2}
   \]
10. Convert to \( (x+1) \) in \( \mathbb{F}_2 \):
    \[
    (x+1)^n + (x+1)^{n-k+2}
    \]
11. Use Lucas's theorem to count the number of odd coefficients in \( (x+1)^n + (x+1)^{n-k+2} \).

The final answer is \( \boxed{2017} \).