A randomly-generated counterexample is:

which has $$M_G=\{0,0,0,0,0,0,2,2\}$$ which is not graphical. (I marked the vertices with their degrees.)

I should also acknowledge that the above counterexample gives rise to an infinite family of counter-examples:

- Take a connected cubic graph, which exist on $n$ vertices for even $n \geq 4$.
- Delete an edge (one that doesn't disconnect the graph, which must exist, since the graph is not a tree).
- Add pendant vertices to the newly created vertices of degree $2$.

This gives a connected graph with degree sequence $(1,1,3,3,\ldots,3)$ and hence we have $M_G=\{0,0,\ldots,0,2,2\}$.

graphical? – Benoît Kloeckner Aug 23 '13 at 11:19