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 .