a. All $(n,k)$ with $k \le 2$, and only those. If $k \le 2$, since two edges may not connect the same pair of vertices, at least one endpoint of each of these edges is a leaf. Toggle the leaves. If $k \ge 3$, consider any graph that has a triangle $abc$, and look at these three edges. Any toggle of $a,b,c$ will change the state of an even number of them (and toggle of any other vertex doesn't change these edges), so the parity of the number of red edges remains the same. Initially it's odd (3), but at the end it's even (0), impossible.

b. All $(n,k)$ with $k \le \frac{n^2}{4}$, and only those. First, to show that they are possible: Divide the vertices into two groups of as equal sizes as possible (that is, one is $\left\lfloor \frac{n}{2} \right\rfloor$ and the other is $\left\lceil \frac{n}{2} \right\rceil$), and only draw edges between these; draw any $k$ edges. Toggling all vertices of one group makes all edges blue, so this is valid. Also, by dividing into cases ($n$ even and $n$ odd), we can show that $\left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lceil \frac{n}{2} \right\rceil = \left\lfloor \frac{n^2}{4} \right\rceil$, so any such $k$ can be done. Showing that no larger $k$ works is easy: by Turan's theorem, a graph with more than $\frac{n^2}{4}$ edges has a triangle, and by applying the reasoning from before this graph can never be solved.

part a is almost correct, except that G is connected, so k<=2 might not be sufficient.

Oops, okay. a. $(n,n-1)$ for all $n \ge 3$. If there are more than $n-1$ edges, we can simply construct a triangle and add the remaining edges together to make a connected graph. Since there's a triangle, it's impossible for the same reason as above. If there are $n-1$ edges, the graph is a tree and hence bipartite; toggle all vertices of one side.