Given a maximal degree $k$ and maximal diameter $d$. We identify 3 nodes, $i$, $j$, and $v$. Can an undirected graph exist, such that:

  • all nodes but $v$ have full degree $k$ ($v$ having a lower degree),
  • the distance between $i$ and $j$ is exactly $d+1$,
  • the distance between $i$ and $v$, and the distance between $j$ and $v$ is exactly $d$,
  • all other distances in the graph are at most $d$.

The distance is measured in the number of nodes that have to be visited on the shortest path between the two nodes.

My intuition would say no, but I'm looking forward to a proof!

  • 1
    $\begingroup$ I think we need at least $k\ge 3$, but I guess this was some implicit assumption. Is it intentional that your distance definition sets two adjacent vertices at distance two? Could you explain a bit about why your intuition says no? $\endgroup$
    – M. Winter
    Oct 31, 2018 at 17:11

1 Answer 1


It is not impossible in general. Here is a graph with $k=3$ and $d=10$ (if I understood your distance definition correctly).

Note that the colored vertices are the ones farthest away from the central vertex (for their resp. "component"). This helps in verifying that the distance of any two vertices other than $i$ and $j$ is always $\le d$.


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.