0
$\begingroup$

I'm finding distance and diameter confusing in graph theory. Distance is the smallest path between two vertices. Diameter is the largest smallest path? Is it possible for a connected graph to have a diameter greater than the largest distance between any two vertices?

$\endgroup$
  • $\begingroup$ Strictly greater? No. If you want a rewording, let $d(u,v)$ be the distance function, $d(u,v)=$ distance between $u$ and $v$ (i.e. the length of the shortest path between $u$ and $v$). Then diameter is $\max\limits_{u,v\in V}\{d(u,v)\}$. The largest distance between two vertices is still a distance between two vertices and so is considered when taking the maximum implying that the maximum is at least as large. It is certainly possible to have a path between two vertices of length greater than the diameter, but if that were the case then cannot be the shortest path between them. $\endgroup$ – JMoravitz Nov 27 '17 at 20:37
  • $\begingroup$ Okay, then if I had graph G where $e(x)=\underset{y \in V(G)}{\text{max}}\{d(x,y)\}$, is it possible for G to have a diameter of 6 if $e(x)=3$? $\endgroup$ – Maggy Wood Nov 27 '17 at 20:49
  • $\begingroup$ Yes, of course. Consider the following graph o-o-o-x-o-o-o (where o's represent normal vertices and x represents our special vertex $x$). The furthest away from x you can get is $3$ but the furthest distance between any two vertices in this case would be the furthest left and furthest right as pictured and is $6$. Remember that diameter has to do with every pair of vertices, not just those pairs having to do with some specifically named vertex. $\endgroup$ – JMoravitz Nov 27 '17 at 20:51
  • $\begingroup$ So x is a specific vertex and not representative of all the vertices in the graph. $e(x)$ doesn't mean that the max distance between all two vertices is 3? $\endgroup$ – Maggy Wood Nov 27 '17 at 20:59
  • $\begingroup$ Think of the relation to geometry. If you want to measure the diameter of a circle, you would measure from one end of the circle to the other. You wouldn't measure from somewhere in the middle of the circle to the outside. Similarly to how diameter is defined for graph theory, the diameter of a circle is also the largest distance between two points in the circle. $\endgroup$ – JMoravitz Nov 27 '17 at 20:59
0
$\begingroup$

"largest distance between any two vertices" is an alternative definition for diameter.

At least when the graph is connected, but talking about diameter in unconnected graphs is not common.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.