To delete vertices on a polygon mesh you must use the Delete Edge/Vertex feature (Delete Edge/Vertex).
Many
            types of polygon vertices cannot be deleted using the   key. For
            example, while you can delete border vertices on the exterior of
            a mesh using the
  key. For
            example, while you can delete border vertices on the exterior of
            a mesh using the   key
            when the selected vertex shares only two edges, you cannot use the
  key
            when the selected vertex shares only two edges, you cannot use the   key
            to delete a vertex when it shares more than two edges.
  key
            to delete a vertex when it shares more than two edges.
         
When an interior vertex is deleted using Delete Edge/Vertex, any edges associated with the deleted vertices are also removed as a result. The polygon faces surrounding the deleted vertex are replaced with a single n-sided polygon created from the vertices surrounding the deleted vertex. Maya does not use quads and triangles in the affected area in order to reduce the number of polygons.
This action is equivalent to selecting all the edges surrounding the vertex and deleting them.
When
            the edges of a polygonal mesh are deleted using the   key the
            selected edge is deleted but not the shared vertices at either ends
            of the edge. if you want to delete the shared vertices associated
            with the deleted edges you must use 
                     Edit Mesh > Delete Edge/Vertex.
            You can only delete interior edges on a mesh using the Delete
               Edge/Vertex feature.
  key the
            selected edge is deleted but not the shared vertices at either ends
            of the edge. if you want to delete the shared vertices associated
            with the deleted edges you must use 
                     Edit Mesh > Delete Edge/Vertex.
            You can only delete interior edges on a mesh using the Delete
               Edge/Vertex feature.
         
To delete edges and the associated shared vertices

Troubleshooting Delete Edge/Vertex
If
                     you try to delete interior vertices with the   key,
                     Maya will display a warning message that it cannot delete the vertices because
                     they have “complex edge attachment”. That is, the vertices are connected
                     to more than two edges.
  key,
                     Maya will display a warning message that it cannot delete the vertices because
                     they have “complex edge attachment”. That is, the vertices are connected
                     to more than two edges.
                  
Instead, select the vertices and choose Edit Mesh > Delete Edge/Vertex, or only select vertices that reside at a corner or are connected to two edges only.
