## Connectedness

Let be a graph.

A *path* in is a sequence of distinct vertices of , such that for . In this case, we say that the path is a -path and that it has *length* .

We say that a graph is *connected* if for any pair of vertices there is an -path.

The sequence , where is the number of connected graphs on vertices, is considered in this link.

## Distance

The *distance* between vertices is defined as:

,

whenever there is at least an -path.

Observe that if and only if , and that if and only if .

For example, in the following graph (the *cube*):

we have that , since the vertices , are not adjacent and there is an -path with length 2, namely .

## Diameter

If is a connected graph, we define its *diameter* as:

.

The cube graph has diameter 3, since there are two vertices which are at distance 3 and no two vertices are at greater distance.

## Girth

A *cycle* in is a sequence , of distinct vertices of , such that for and . We say that has *length* , and that it is an -cycle. If is an odd number, we say that is an *odd cycle*.

If has at least a cycle, we define the girth of , as:

.

A cycle of length 3 will be also called a *triangle*.

The cube graph has girth , since it has no triangles and has a 4-cycle.

## Exercises

- Show that the relation in , defined by if and only if there is an -path in , is an equivalence relation.
- Determine the graphs that have diameter 0, and the graphs that have diameter 1.
- Determine the diameter and the girth of the
*Petersen graph*: