Let G be the graph:
What is the diameter of $G$?
According to Wikipedia:
To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph
Solution:
Okay, so lets find the length of the shortest paths between all possible pairs of vertices, we have:
- $a \rightsquigarrow b$: 1
- $a \rightsquigarrow c$: 2
- $a \rightsquigarrow d$: 1
$a \rightsquigarrow e$: 3
$b \rightsquigarrow a$: 3
- $b \rightsquigarrow c$: 1
- $b \rightsquigarrow d$: 1
$b \rightsquigarrow e$: 2
$c \rightsquigarrow a$: 2
- $c \rightsquigarrow b$: 1
- $c \rightsquigarrow d$: 2
$c \rightsquigarrow e$: 1
$d \rightsquigarrow a$: 1
- $d \rightsquigarrow b$: 2
- $d \rightsquigarrow c$: 2
$d \rightsquigarrow e$: 1
$e \rightsquigarrow a$: 1
- $e \rightsquigarrow b$: 1
- $e \rightsquigarrow c$: 1
- $e \rightsquigarrow d$: 1
The greatest lengths from path lengths above is 3. Thus the diameter of $G$ is 3?
$\endgroup$ 11 Answer
$\begingroup$As commented: Yes, that is correct. You could descirbe the diamter of a graph $G$ such as $\operatorname{diam}(G) = \max\min d_G(x,y)$, where $d$ is the distance function in $G$ and the $\max\min$ is taken over all vertices $x,y \in G$.
$\endgroup$
