I would like to measure the similarity between a pair of weighted tree graphs. According to this [post](https://mathoverflow.net/a/38316/145438), this can be done by regarding the trees as metric spaces and then applying the Gromov-Hausdorff distance. 


Given two metric spaces, $(A, d\_{A})$ and $(B, d\_{B})$, the Gromov-Hausdorff distance is defined:


$$d\_{GH}(A,B)=\inf\limits\_{f:A\rightarrow M\\ g:B\rightarrow M}d\_{H}(f(A), g(B))$$


where $f:A\rightarrow M$ and $g:B\rightarrow M$ are isometric embeddings of $A$ and $B$ into some metric space $M$, respectively. My question is: if the infimum is taken over all possible such embeddings, and there is an infinity of such embeddings, then how can one compute this distance? 


Moreover, in [this paper](https://www.researchgate.net/publication/51716861_Computing_the_Shape_of_Brain_Networks_Using_Graph_Filtration_and_Gromov-Hausdorff_Metric) the authors took the approach described above to compare between brain networks and defined $f:A\rightarrow B$ and $g:B\rightarrow A$. That is, no common metric space $M$ is involved. What allows to discard M when using the Gromov-Hausdorff metrics?


Thanks a lot for your time.



Gromov-Hausdorff distance between weighted tree graphs
I would direct you to Theorem 7.3.25 of the book "A Course in Metric Geometry" by Burago-Burago-Ivanov.


Roughly speaking, the Gromov-Hausdorff distance between two compact metric spaces can be computed by looking for the infimum of all $\epsilon>0$ such that there is a correspondence between $X$ and $Y$ that changes distances by an additive error of at most $\epsilon$. See the above reference for a more precise statement.


