## Vertex Mutable Graph

A vertex mutable graph can be changed by adding or removing vertices. The memory management is the responsibility of the graph implementation. The graph user need only make calls to `add_vertex` and `remove_vertex` and the graph implementation does the rest.

### Refinement of

Graph and DefaultConstructible

### Associated Types

No additional associated types.

### Valid Expressions

- `add_vertex(g)` returns `vertex_descriptor`
  Semantics: Add a new vertex to the graph. The `vertex_descriptor` for the new vertex is returned.
- `remove_vertex(u, g)` returns `void`
  Semantics: Remove u from the vertex set of the graph.
  Preconditions: u is a valid vertex descriptor of graph g and there are no edges incident to vertex u. The function `clear_vertex` can be used to remove all incident edges.
  Postconditions: `num_vertices(g)` is one less; u no longer appears in the vertex set of the graph and it is no longer a valid vertex descriptor.

### Complexity guarantees

- Vertex insertion is guaranteed to be amortized constant time.
- Vertex removal is at most `O(|E| + |V|)`.

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu)