I can't understand what is a normal tree. In the textbook, it says that a rooted tree T contained in a graph G is called normal in G if the ends of every T-path in G are comparable in the tree-order of T. However, if I choose any vertex of T, and order a tree with a root that I chose, then that tree is a normal tree, because the ends of any T-path are comparable!! I want to know what did I misunderstood. Furthermore, can someone show me a counterexample that a tree with some root does not become a normal tree?
$\endgroup$2 Answers
$\begingroup$You haven't said what the textbook is, but your definition appears off; it makes more sense to define (as is done here for example) a tree to be normal if the ends of every edge of $G$ are comparable in the tree order.
So, to take a simple example, consider the complete graph on vertices $\{a,b,c,d\}$.
- The tree with edges $ab, bc, cd$ (a path) and root $a$ is normal. Here, the tree order is actually a linear order: $a < b < c < d$. Any two vertices are comparable, and so the ends of any edge of $G$ are comparable.
- The same tree with edges $ab, bc, cd$ stops being normal if we take $b$ to be the root. Now we have $b < a$ and $b < c < d$, but $a$ and $c$ (for example) are not comparable, so the normality condition is violated for edge $ac$.
- The tree with edges $ab, ac, ad$ (a star) isn't normal with any root. The ends of at least one of the edges $bc, bd, cd$ will not be comparable in the tree order.
In fact, as the link earlier mentions, for finite graphs $G$, the normal trees are precisely the trees you get by depth-first search starting from a vertex (taking that vertex to be the root).
$\endgroup$ $\begingroup$Yeah I saw the same definition. I'm assuming the text is GTM Diestel. I also got confused.
The definition seems to be off. Here is the correct definition:
A tree $T$ rooted at $r$ is normal in $G$ if for each $e=uv\in E(G)\cap {V(T)\choose 2}$, either $u\in rTv$ or $v\in rTu$. In other words $u,v$ must have a ancestor-descendant relationship in $T$ with root $r$. Note that the result is trivial if $e\in V(T)$.
Notation: $xTy$ denotes the unique $x$-$y$ path in $T$.
There is no need to use up all $V(G)$, or even take $G$ to be connected.
$\endgroup$
