SKEDSOFT

CONNECTED AND DISCONNECTED GRAPHS: A graph G is said to be a connected if every pair of vertices in G are connected. Otherwise, G is called a disconnected graph. Two vertices in G are said to be connected if there is at least one path from one vertex to the other.

In other words, a graph G is said to be connected if there is at least one path between every two vertices in G and disconnected if G has at least one pair of vertices between which there is no path. A graph is connected if we can reach any vertex from any other vertex by travelling along the edges and disconnected otherwise.
For example, the graphs in Figure 30(a, b, c, d, e) are connected whereas the graphs in Figure 31(a, b, c) are disconnected.

A complete graph is always connected, also, a null graph of more than one vertex is disconnected (see Fig. 32). All paths and circuits in a graph G are connected subgraphs of G.

Every graph G consists of one or more connected graphs, each such connected graph is a subgraph of G and is called a component of G. A connected graph has only one component and a disconnected graph has two or more components. For example, the graphs in Figure 31(a, b) have two components each.

Path graphs and cycle graphs: A connected graph that is 2-regular is called a cycle graph. Denote the cycle graph of n vertices by Γn. A circuit in a graph, if it exists, is a cycle subgraph of the graph. The graph obtained from Γn by removing an edge is called the path graph of n vertices, it is denoted by Pn.

The graphs Γ6 and P6 are shown in Figure 33(a) and 33(b) respectively.

Rank and nullity: For a graph G with n vertices, m edges and k components we define the rank of G and is denoted
by ρ(G) and the nullity of G is denoted by μ(G) as follows.
ρ(G) = Rank of G = n – k
μ(G) = Nullity of G = m – ρ(G) = m – n k
If G is connected, then we have
ρ(G) = n – 1 and μ(G) = m – n 1.