Normal tree(Graph Theory)

Question

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?

Answer 1

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).

Answer 2

I saw the same definition in Graph Theory by Diestel. I guess you misunderstand the meaning of tree-order. It doesn't mean you order vertexs like $\{1,2,3\dots n\}$, in fact, we write $x\leq y$ for $x\in rTy$, it defined a partial ordering on $V(T)$, not totally ordering on $V(T)$. Maybe it will be helpful to explain why the example gived by Diestel is a normal tree, and we will construct a non-normal tree from it, hence we get a counterexample. Every $T$-path in $G$ is a thin line, if we denote ends of $T$-path by x and y, and you can find a path $rTxTy$, it means you can compare x and y, hence it is a normal tree by definition. Now consider this graph. It isn't a normal tree, you can find a $T$-path($v_1v_2$), those ends can't lie on $rTx$ for every $x\in V(T)$ together, it is means you can't compare them, hence it isn't a normal tree.

Answer 3

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.