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.
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 .
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.
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.
- 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: