Connected Graphs

A graph is called connected if given any two vertices $P_i, P_j$, there is a path from $P_i$ to $P_j$.

The following graph ( Assume that there is a edge from $p_5$ to $P_3$.) is a connected graph. Because any two points that you select there is path from one to another. later on we will find an easy way using matrices to decide whether a given graph is connect or not.

Figure 8

The graph shown below ( Figure 9 ) is not a connected graph.

Figure 9

The graph shown above is not a connected graph, because there is no path from $P_3$ to $P_1$. Also there is no path from $P_4$ to $P_3$.

Definition

If there is a path from $P_i$ to $P_i$ ( from a point to itself ), the path is called a loop.

In the following graph there is loop from $P_1$ to itself.

Figure 10

Also the same loop may be considered as the path $P_3 \rightarrow P_1 \rightarrow P_3$ which is again forms a loop.

Exercise:

In the following graph find all the loops.

Figure 11