4. Connectivity
In Chapter 2 we gave a simple definition for connected graphs and also defined the component of a graph. Since we use these terms again, now we repeat the definitions:
A graph is
connected if every two of its vertices are connected. Otherwise the graph
is disconnected. Each subgraph
induced by the connected vertices is called a connected component of G. The number of components of G
is denoted by .