Let $X=(V,E)$ be a finite, connected, regular graph with diameter $D$. Is it true that, for every $x\in V$, there exists $y\in V$ such that $d(x,y)=D$? (the answer is clearly yes if $X$ is vertex-transitive).

  • 1
    $\begingroup$ What about this one: vertices P, A, B, C, X, Y, Z, U, V, W, edges PU, PV, PW, UA, UX, VB, VY, WC, WZ, BC, CA, AB, VW, WU, UV ? Everything reachable in 2 edges from P, but diameter apparently 3. $\endgroup$ – darij grinberg May 11 '11 at 21:30
  • $\begingroup$ A bipartite counterexample might be more interesting. $\endgroup$ – darij grinberg May 11 '11 at 21:35
  • 2
    $\begingroup$ Here's a bipartite example: vertices A B 0 1 2 3 4 5 6 7 8 9, edges 0A, 0B, 01, 12, 13, 2A, 24, 3B, 35, 46, 47, 58, 59, 78, 79, 68, 69. This leaves vertices A and B with degree two. Build two of these graphs and add edges between the corresponding copies of A and B. I really wish you could edit comments. $\endgroup$ – Clinton Conley May 11 '11 at 21:43
  • $\begingroup$ Thanks to all for your nice examples! They illustrate the fact that regularity does not imply symmetry! BTW, it seems that Darij's example is not regular ($X,Y,Z$ being terminal vertices). Let me mention that I just asked a related question on mathoverflow.net/questions/64746/… $\endgroup$ – Alain Valette May 12 '11 at 5:25
  • $\begingroup$ Oh sorry, replace VW, WU, UV by YZ, ZX, XY. It's hard to work with a sketch too small to label the points properly. $\endgroup$ – darij grinberg May 12 '11 at 11:32

Counter-example http://www.freeimagehosting.net/uploads/9a4165cab4.png The diameter is 8, but 1 is centered with at most 5 as distance to every other.

  • $\begingroup$ If you have access to sage or other sparse6-format readers, you can get the graph by the given string. sage: g.sparse6_string() ':U___d@C`DecFcFGjAIaJkiLiLMpBObPqoRoRS' $\endgroup$ – Pål GD May 11 '11 at 21:55
  • $\begingroup$ And if you're careful, you can produce a bipartite counterexample, as Darij wanted. $\endgroup$ – James Cranch May 12 '11 at 9:23
  • $\begingroup$ The link to the image seems to be broken. $\endgroup$ – jeq Sep 26 '17 at 13:47

Imagine taking a long thin sausage, and drawing four lines from one end to the other end, so that each end of the sausage looks like a cross shape. Then draw a huge number of circles around the sausage.

We've constructed a finite, connected, 4-regular graph. But the diameter is the distance between the endpoints, and the things in the middle of the sausage are genuinely in the middle.

Does that make any sense at all as a counterexample?

A similar construction (where the end of the sausage looks like a hash-sign) gives a bipartite counterexample.


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.