In this chapter, the concept of graph connectivity is introduced. In the first section, some concepts such as walk, path, component and connected graph are defined, and connectedness of a graph from the viewpoint of vertex connectivity, and also, edge connectivity are discussed. Then, blocks and block tree of graphs are illustrated. In addition, connectivity in directed graphs is introduced. Furthermore, in the last section, two graph traversal algorithms, depth first search and breadth first search, are described to investigate the connectedness of directed and undirected graphs.
TopConnected Graphs
Before discussing connectivity in graph theory, it is required to define some concepts. Following are the definitions of concepts, which will be used in this chapter.
A walk can be illustrated as a sequence W:= v0e1v1… vk-1ekvk, in which edge ei connects vertices vi-1 and vi. If v0 and vk are the same, the walk is closed. In a graph G, connectivity of pairs of vertices is the equivalence relation on V. Obviously, a vertex such as x, can be connected to itself through a trivial walk W:= x. In addition, a walk which connects x to y, also connects y to x, reversely. Furthermore, the walk W, which connects x and y and the walk W', which connects y and z can be combined, making the sequence xWyW'z, to connect x and z. Thus, when x is concatenated to y and y is concatenated to z, then x and z are concatenated too. Applying the definition of a walk, a graph, which is nonempty, is a connected graph if for every pair of vertices vi and vj, there is a walk from vi to vj (Bollobás, 1998).
Furthermore, a path can be defined as a nonempty graph, P = (V, E), in which V = {x0, x1, …, xk} and E={x0x1, x1x2, …, xk-1xk}. It concatenates vertices sequentially so that connects x0 and xk. Accordingly, a path is a walk in which no vertex appears more than once. Applying the definition of a path, the graph G is addressed connected if any pair of its vertices is concatenated by a path in it (Diestel, 2006).
Finally, a component of a graph G = (V, E), is a maximal connected subgraph of it. Therefore, a component, which is connected, is always nonempty. In addition, the empty graph has no components. Hence, we can conclude that graph G is connected if and only if it has just one component (Bollobás, 1998).
Proposition 1: The vertices of a connected graph G can always be enumerated, say as v1, …, vn, so that Gi:= G[v1, …, vi] is connected for every i.
Proof: Choose a vertex as v1, and inductively suppose v1, …, vi have been selected for some i < |G|. Then select a vertex v 
G - Gi. Regarding G is connected; it should include the v - v1 path. Set vi+1 the last vertex of v - v1 path in G - Gi; therefore vi+1 has a neighbor in Gi and Gi+1 can be formed using it. The connectivity of each Gi is followed by induction on i (Diestel, 2006).