1
$\begingroup$

Let $\Gamma$ be a finite, connected graph (multiple edges between two vertices are allowed). Fix a vertex $u_0\in V\Gamma$.

Does there exist a maximal subtree (i.e., a spanning tree) $T\subset\Gamma$ such that $ |d_T(\alpha(e),u_0)-d_T(\omega(e),u_0)|\leq1 \quad\text{for all edges } e\in E\Gamma\setminus ET? $ (Here $d_T$ is the path metric in $T$, and $\alpha(e)$ and $\omega(e)$ are the initial and terminal vertices.)

If such a subtree does not exist in general, does this at least hold for planar graphs $\Gamma$?

I have tried induction arguments, but the details don't seem to work out. Can someone give me a hint as to what to try?

  • 1
    The claim is clearly true if $\Gamma$ is a cycle.2012-04-30

1 Answers 1

2

Call $V_n=\{x\in V\Gamma\mid d_\Gamma(u_0,x)=n\}$ and define recursively the generations of $T$ as follows. The vertices in the $n$th generation of $T$ are exactly the vertices in $V_n$. If the edges between $V_k$ and $V_{k+1}$ in $T$ are known for every $k\leqslant n-1$, define the collection of edges between $V_n$ and $V_{n+1}$ in $T$ as any maximal subset of the edges in $\Gamma$ between $V_n$ and $V_{n+1}$ such that the resulting graph is still a tree. Equivalently, for each $x$ in $V_{n+1}$, choose exactly one vertex $y$ in $V_n$ such that $\{x,y\}$ is an edge of $\Gamma$ and add $\{x,y\}$ as the only edge in $T$ between $x$ and $V_{n}\cup V_{n+1}$.

By construction, $T$ is indeed a tree, $VT=V\Gamma$ and $d_T(u_0,x)=d_\Gamma(u_0,x)$ for every $x$ in $V\Gamma$, hence $T$ is a spanning tree of $\Gamma$ such that the property you are interested in holds.

  • 0
    Thanks, Didier. I think your answer is correct.2012-05-01