**Vertex connectivity and edge connectivity**

To determine the *vertex connectivity* of a graph, we ask the question: what
is the minimum number of vertices that we must remove from the graph to
disconnect it?

Since, by definition, an edge connects two vertices, when a vertex is removed from a graph, all of the edges incident with that vertex must also be removed. These edges cannot be arbitrarily connected to other vertices.

This graph has vertex connectivity of 1:

This graph has vertex connectivity of 3:

This graph has vertex connectivity 5:

You cannot split a complete graph into two disconnected components by simply removing vertices. Removing successive vertices ultimately reduces the graph to a single vertex. So for complete graphs, the connectivity is measured by counting the number of vertices that must be removed to reduce the graph to a single vertex.

To determine the *edge connectivity* of graph, we ask the question, what is
the minimum number of edges that we can remove from the graph to disconnect
it?

This graph has edge connectivity of 1: | |

This graph has edge connectivity of 2: | |

This graph has edge connectivity of 3: |

Notice that deleting an edge from a graph does not require you to delete any vertex in the way that deleting a vertex requires you to also delete the incident edges.

Copyright © 1999-2000 SciMathMN