ABSTRACT
We saw in Chapter 3 that each tree of order 3 or more contains at least one vertex whose removal results in a disconnected graph. In fact, every vertex in a tree that is not a leaf has this property. Furthermore, the removal of every edge in a tree results in a disconnected graph (with exactly two components). On the other hand, no vertex or edge in a nonseparable graph of order 3 or more has this property. Hence, in this sense, nonseparable graphs possess a greater degree of connectedness than trees. We now look at the two most common measures of connectedness of graphs. In the process of doing this, we will encounter some of the best known and most useful theorems dealing with the structure of graphs.
The first measure of graph connectedness that we discuss is expressed in terms of the removal of vertices from a graph.
