Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Consider a cyclic graph – Lieven Apr 30 '12 at 14:03
The claim is clearly true if $\Gamma$ is a cycle. – David Apr 30 '12 at 14:16
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks, Didier. I think your answer is correct. – David May 1 '12 at 1:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.