The graphs under consideration in this section are assumed to be simple. In the preceding application to a communication network, we left aside a quite important practical aspect: the vulnerability of the network, that is its capacity to withstand the failure of some of its links or centers.

In terms of graphs, we consider, for example for a connected graph, the largest number of edges it is possible to remove without the graph losing its property of connectedness. With the idea of bridges we have seen this type of property earlier in this chapter. The equivalent exists for vertices.

A cut vertex of a graph G is a vertex x such that G − x has at least one more connected component than G. This idea leads to a classic and useful decomposition of graphs.

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(59)