ABSTRACT
Trees are the smallest connected graphs. For deleting any edge will disconnect a tree.
The following figure shows three graphs in order of increasing connectivity.
κ = 1 κ = 2 κ = 4 κ′ = 1 κ′ = 3 κ′ = 4
FIGURE 7.1
Three graphs with increasing connectivity
The second graph can be disconnected by deleting the two shaded vertices, but
three edges must be deleted in order to disconnect it. The third graph is complete and
cannot be disconnected by deleting any number of vertices. However, the deletion of
four edges will do so. Thus, connectivity is measured by what must be deleted from
a graph G in order to disconnect it. Because one can delete vertices or edges, there will be two measures of connectivity.
