# Existence of a graph with strong restrictions

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!

• 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? – M. Winter Oct 31 '18 at 17:11

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$$.