## Connectedness

Let $G$ be a graph.

A path $P$ in $G$ is a sequence $P=(v_0, v_1,\ldots,v_n)$ of distinct vertices of $G$, such that $v_i\sim v_{i+1}$ for $i=0,1,\ldots,n-1$. In this case, we say that the path $P$ is a $v_0v_n$-path and that it has length $n$.

We say that a graph $G$ is connected if for any pair of vertices $u,v\in V(G)$ there is an $uv$-path.

The sequence $(a_n)$, where $a_n$ is the number of connected graphs on $n$ vertices, is considered in this link.

## Distance

The distance $d(u,v)$ between vertices $u,v\in V(G)$ is defined as:

$\displaystyle d(u,v)=\min\{\textrm{length of }P\mid P \textrm{ is an }uv\textrm{-path}\}$,

whenever there is at least an $uv$-path.

Observe that $d(u,v)=0$ if and only if $u=v$, and that $d(u,v)=1$ if and only if $u\sim v$.

For example, in the following graph $G$ (the cube):

we have that $d(a_0,a_2)=2$, since the vertices $a_0$, $a_2$ are not adjacent and there is an $a_0a_2$-path with length 2, namely $P=(a_0,a_1,a_2)$.

## Diameter

If $G$ is a connected graph, we define its diameter $\textrm{diam}\,G$ as:

$\displaystyle \textrm{diam}\,G=\max\{d(u,v)\mid u,v\in V(G)\}$.

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

## Girth

A cycle $C$ in $G$ is a sequence $C=(v_1,v_2,\ldots,v_n)$, $n\geq3$ of distinct vertices of $G$, such that $v_i\sim v_{i+1}$ for $i=1,\ldots,n-1$ and $v_1\sim v_n$. We say that $C$ has length $n$, and that it is an $n$-cycle. If $n$ is an odd number, we say that $C$ is an odd cycle.

If $G$ has at least a cycle, we define the girth $g(G)$ of $G$, as:

$\displaystyle g(G)=\min\{\textrm{length of }C\mid C \textrm{ is a cycle in }G\}$.

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

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

## Exercises

1. Show that the relation $\approx$ in $V(G)$, defined by $u\approx v$ if and only if there is an $uv$-path in $G$, is an equivalence relation.
2. Determine the graphs that have diameter 0, and the graphs that have diameter 1.
3. Determine the diameter and the girth of the Petersen graph: