Understanding the proof of Diestel's Lemma 1.5.5 (i) concerning a normal tree T in a graph G and comparability of nodes w.r.t. the tree-order

60 Views Asked by At

I have problems understanding the minimal vertex sequence $x = t_1 > \dots > t_k < \dots < t_n = y$ used in the proof of Diestel's Lemma 1.5.5 (i) (see Link).

To quote its definition:

Let $T$ be a normal tree in a graph $G$ and $x$,$y$ any two vertices $x$,$y \in T$ that are incomparable in its tree. Let $P$ be any $x$-$y$ path in $G$. Let $t_1, ..., t_n$ be a minimal sequence of vertices in $P \cap T$ such that $t_1 = x$ and $t_n = y$ and $t_i$ and $t_{i+1}$ are comparable in the tree-order of $T$ for all $i$.

It then goes on to show that this implies $$x = t_1 > \dots > t_k < \dots < t_n = y$$ I do very well understand why $t_{i-1} < t_i > t_{i+1}$ is not possible (see also this question) as comparability of $t_{i-1}$ and $t_{i+1}$ follows by both being an elment of $rTt_i$ and hence, the sequence would violate minimality ($t_i$ could be removed).

However, lets assume $t_{i-1} > t_i > t_{i+1}$. Wouldn't $t_{i-1} > t_{i+1}$ follow from transitivity? Or from a graph theoretic argument: As $t_i$ is an element of the up-closure of $t_{i+1}$ it follows that $t_{i+1} \in rTt_i$ and because $t_i \ne t_{i+1}$, $t_i$ lies at a higher level in $T$. Now, $t_{i-1}$ is in the up-closure of $t_i$, hence $t_i \in rTt_{i-1}$ (and again $t_{i-1} \ne t_i$). But because $T$ is a tree, any two vertices of $T$ are linked by a unique path in $T$ (otherwise $T$ would include a cylce). Hence, $rTt_i \subset rTt_{i-1}$ as both paths include a subpath from $r$ to $t_i$ and $t_i \ne t_{i-1}$. But this implies that $t_{i+1} \in rTt_{i-1}$ as well and hence, $t_{i+1}$ and $t_{i-1}$ are again comparable. With this reasoning, the minimal vertex sequence looks as follows: $x = t_1 > t_2 < t_3 = y$.

So I am wondering, where my reasoning went wrong, and what parts of the tree-order concept I have still not understood.

EDIT: From my understanding now, for the proof in Diestel specifying the $k$ is not necessary. Therefore, I think it was just not bothered to show that $k=2$. But I am still very open to an answer proofing me wrong or affirming my $k=2$ argument.