Why does Skin modifier give No valid root vertex error when placed after Decimate modifier?
This behaviour is based on the modifieirs' stack order. The error Skin modifier provided means that Decimate modifier which most likely is placed above in the stack already deleted the vertex used by Skin modifier as a root one (it doesn't mean that all the vertices of the mesh were deleted; it's just that vertex marked as root one was so lucky to be decimated). From manual about the Skin modifier:


  Marking a vertex as root causes that vertex to be used for calculating rotations for connected limbs. [...] Each set of connected vertices should have one root node. 


So Skin needs one vertex to be marked as root one.

There are some ways to workaround this.


Enter Edit mode of the mesh with both modifiers added, select one of the vertices and mark it as root manually; chances are that it will be the vertex which won't be decimated. If it isn't really important for your mesh to have some certain vertex to be as root one for calculations this should work.
Place the Decimate below the Skin (but this means that the result will change quite a bit, i.e. all the internal faces will be skinned).
Decrease amount of faces to be deleted by Decimate modifier. This is done in different way depending on the modifier's mode, if using Planar you will decrease Angle setting. The less vertices will be decimated, the more chances that one needed for the Skin will remain untouched.