When M is odd, the answer is at least 2.
In this case, if there is a vertex with odd degrees, just divide it into set 2 and others into set 1. So set 2 contains no edges and set 1 contains odd-odd=even edges. So the answer is 2.
The last case is that M is odd and all vertices have even degrees.
First its answer is not 2.
If we try to divide it into 2 sets, let’s name the number of edges in set 1 and set 2 A and B, and name the number of remaining edges C. Because all degrees are even, 2A+C and 2B+C are even, too. So we got C is even. When C is even, A+B=M-C is odd, so either A is odd or B is. This doesn’t meet the constraints.
So for the rest cases the answer is at least 3, and we can soon find that answer is 3.
The solution is find any of the edge, assume it connect u and v, so we divide u and v into set 2 and set 3, and all other vertices into set 1. In this case there are \mathrm{degree}(u) + \mathrm{degree}(v)-1 edges belonging to no sets. This is odd so the number of edges in set 1 is even.
Thanks for this (and sorry the forum software mangled my Quote of your post so badly XD) - I was racking my brains trying to think of a proof of this - looks like I was on completely the wrong track XD
Edit:
Incidentally - I managed to completely misread the question the first time around and in particular (somehow!) misread the definition of “deliciousness” as "If in each subgraph, each vertex has an even number of edges, then Chef thinks that this way of dividing the graph is delicious ", and noticed that in this case, 2 subgraphs are always (based on extensive randomised testing, at least) sufficient - can anyone prove this, and maybe come up with an efficient way to compute the decomposition into subgraphs?
