Question regarding normal spanning trees and a proof of existence

982 Views Asked by At

I'm reading about normal spanning trees in the Diestel book and i am somewhat confused by a number of things i'll try and work in chronological order.

The first thing you need to know is about a tree order.

" Choosing a root $r \in T$ in a tree imposes a partial ordering on $V(T)$ associated with $T$ and $r$ by letting $x \leq y$ if $x \in rTy$ " (i.e $x$ lies on a path from the root to $y$).

The first thing that confuses me is the initial definition it says

"A rooted tree $T$ contained in a graph $G$ is $\textit{normal}$ in $G$ if the ends of every $T$-path in $G$ are comparable by the tree-order of $T$.

What exactly do they mean by a $T$ path? For example given two leafs (neither of them is the root $r$) of any tree $T$ say $x$ and $y$ there is a path from $x$ to $y$ in $T$ but $x$ and $y$ are clearly not comparable. So does a $T$ path mean something else?

The next question i have is regarding the proof of the following proposition, i'll write the proof up to the point where i am confused.


$\textbf{Proposition}$: Every connected graph contains a normal spanning tree with any specified vertex as it's root.

proof: Let $G$ be a connected graph and $r \in G$ any specified vertex. Let $T$ be a maximal normal tree with root $r$ in $G$; we show $V(T)=V(G)$.

Suppose not, and $C$ be a component of $G-T$. As $T$ is normal, $N(C)$ is a chain in $T$.


I don't understand why $N(C)$ is a chain (to clarify $N(C)$ is the neighbourhood of $C$ in $V \setminus C$ and a chain is a set of vertices which are all pairwise comparable.) If for example $x$ and $y$ are two leaves in $T$ i don't necessarily understand why they both can't be in $N(C)$.

I really appreciate any help!! Thanks.

1

There are 1 best solutions below

0
On

The fact that $C$ is connected means that if $u$ and $v$ are vertices of $T$ that are in $N(C)$, then there is a $T$-path from $u$ to $v$. Let $A$ be the set of such vertices. As you say in your comment, the normality of $T$ implies that any two vertices in $A$ are comparable and hence that $A$ is a linearly ordered subset of $T$ with respect to the tree order. In other words, $A$ is a chain in $T$.

Finally, note that $A$ actually is $N(C)$: if $v\in N(C)$, then $v\notin C$, so either $v\in T$, or $v$ is in a different component of $G-T$. The latter is impossible, as there are no edges between vertices in different components of $G-T$, so $v\in T$, and $A=N(C)$, as claimed.