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.

Top## Connected 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:*= *v*_{0}e_{1}*v*_{1}*… v*_{k}_{-1}*e*_{k}v_{k}, in which edge *e*_{i} connects vertices *v*_{i}_{-1} and *v*_{i}. If *v*_{0} and *v*_{k} 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 *v*_{i} and *v*_{j}, there is a walk from *v*_{i} to *v*_{j} (Bollobás, 1998).

Furthermore, a path can be defined as a nonempty graph, *P* = (*V, E*), in which *V* = {*x*_{0}, x_{1}, *…, x*_{k}} and *E*={*x*_{0}x_{1}, *x*_{1}*x*_{2}, …, x_{k}_{-1}*x*_{k}}. It concatenates vertices sequentially so that connects *x*_{0} and *x*_{k}. 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 *v*_{1}, *…, v*_{n}, so that *G*_{i}:= *G*[*v*_{1}, *…, v*_{i}] is connected for every *i*.

**Proof:** Choose a vertex as *v*_{1}, and inductively suppose *v*_{1}, *…, v*_{i} have been selected for some *i* < *|G|*. Then select a vertex *v *_{} G - *G*_{i}. Regarding *G* is connected; it should include the *v* - *v*_{1} path. Set *v*_{i}_{+1} the last vertex of *v* - *v*_{1} path in *G* - *G*_{i}; therefore *v*_{i}_{+1} has a neighbor in *G*_{i} and *G*_{i}_{+1} can be formed using it. The connectivity of each *G*_{i} is followed by induction on *i* (Diestel, 2006).