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!