Minimal alpha-Spanning Tree I got a really strange question with a definition that I've never seen before, so I hope someone of you can help me with it:
Let $G = (V,E)$ be a connected graph and $\alpha \in \mathbb{R}$. A graph $H =(V_H, E_H)$ is called an $\alpha$-Spanning Tree of $G$ if $V_H = V$ and $E_H\subseteq E$ and for every vertices the inequality: $d_H(u,v) \leq \alpha \cdot d_G(u,v)$ applies.
My job is to find a preferably small $\alpha > 0$ so that a grid graph $M_{n,n}$ has one $\alpha$-spanning tree for sure.
edit: $d_G$ is the shortest Path of G between two vertices and $d_H$ is the shortest path of graph H between two vertices.

We cannot do better than $\alpha=1$.
If $\alpha<1$, this implies that there exists some path between each pair of vertices $u,v$ on $H$ shorter than the shortest path on $G$. Clearly there can never be such a path, since the edges of $H$ are all in $G$.
If $\alpha=1$, this implies that there exists some path between each pair of vertices $u,v$ on $H$ shorter than or exactly as long as the shortest path on $G$. So just use an $H$ where $E_H=E$, in which case $G$ and $H$ are identical.
