If the edges are deleted via delete-key the vertices will still remain. There is a "delete-edges" when you shift +RMB. With this tool the vertices will be deleted too.
To fix this after you've already deleted the edges, you can select the vertices and hit the Delete key. You can be sloppy with your selection, the Delete command will only delete vertices that have two edges attached to them. Just be careful on quad corners that are also border edges (corners of a tesselated plane for…