A graph is a **minimal graph of diameter $2$** if it has diameter $2$ and the deletion of any edge increases its diameter.


Let $G$ be a minimal graph of diameter $2$, then every edge of $G$ belongs to a path $u$-$v$ in $G$ which is the unique path of length at most $2$ with endpoints $u$ and $v$.


My question is: If $H$ is a graph satisfies every edge of $H$ belongs to a path $u$-$v$ in $H$ which is the unique path of length at most $2$ with endpoints $u$ and $v$. Does there must exist a minimal graph $G$ of diameter $2$ such that $V(G)=V(H)$ and $H$ is a subgraph of $G$?



A question about minimal graph of diameter $2$
If I understand the question correctly, the answer is *no*.


Let $H$ be the 5-vertex graph consisting of a triangle with "tails" on two vertices; more explicitly let $V(H)=\{1,2,3,4,5\}$ and $E(H)=\{\{1,2\},\{2,3\},\{1,3\},\{1,4\},\{2,5\}\}$.


Then $H$ has the stated property: each edge is part of a path of length $\leq 2$ that is the unique such path between its endpoints. Explicitly:


For $\{1,2\}$, take $4\to 1\to 2$ or $1\to 2\to 5$.


For $\{2,3\}$, take $5\to 2\to 3$.


For $\{1,3\}$, take $4\to 1\to 3$.


For $\{1,4\}$ and $\{2,5\}$ take $1\to 4$ and $2\to 5$ respectively.


However, $H$ is not the subgraph of any minimal graph of diameter $2$ on five vertices. In fact, no such graph contains a triangle. Proof, by fully classifying minimal diameter 2 graphs on 5 vert's: if a minimal graph of diameter 2 on five vertices contains a vertex of degree 4, it contains the star $K\_{1,4}$ and then it equals this since this is min. diameter 2. If it contains no vertex of degree $>2$, then it is clearly the $5$-cycle $C\_5$ since again it must contain this graph (otherwise it would have diameter $>2$) and this too is min. diameter 2. Finally, if it contains a vertex of degree $3$ but none of degree $4$, then it must be $K\_{2,3}$ since, say the degree 3 vertex is $a$ and it's adjacent to $b,c,d$. If the final vertex $e$ is connected to only $b$, then $b$ is forced to be degree $4$ to achieve diameter $2$, contradiction; if it's connected only to $b$ and $c$, then to achieve diameter 2 one of them must be connected to $d$ and then the graph contains the $5$-cycle properly and is not minimal. Thus $e$ must be adjacent to $b,c,d$, so the graph contains $K\_{2,3}$, and then it equals this since it is already min. diameter 2.


