Tree ordering and upclosure and downclosure

314 Views Asked by At

I am referring Diestal book on Graph Theory($5^{th}$ Edition)

In section 1.5 defines the following :

Writing x $ < $ y for x ∈ rT y then defines a partial ordering on V (T ), the tree-order associated with T and r. We shall think of this ordering as expressing ‘height’: if x < y we say that x lies below y in T , we call $\lceil y \rceil$ := { x | x $\leq$ y } and $\lfloor x \rfloor$ := { y | y $\geq$ x } the down-closure of y and the up-closure of x

I have a confusion with Lemma 1.5.5 of the Diestal book on Graph Theory($5^{th}$ Edition)which states that:

Let T be a normal tree in G

(i) Any two vertices x, y ∈ T are separated in G by the set $\lceil x \rceil ∩ \lceil y \rceil $.

My doubt is: how $\lceil x \rceil ∩ \lceil y \rceil $ separates x and y?

2

There are 2 best solutions below

2
On BEST ANSWER

In the definition V(T) keeps a partial ordering, is a tree order associated with root element r and tree T. So, consider the r as the least element and all leaves in the tree are the maximal elements.

Consider any two vertices x,y $\in$ V(T) and ⌈x⌉, ⌈y⌉. In each element down closure contains at least root element r(according to the definition of down closure ). If take their ⌈x⌉∩⌈y⌉ it also contains r. If we remove root element, it makes x and y disconnected.

0
On

If x = y, that set includes x and y.
If x < y, that set excludes y, includes x.
In both cases, thought usually disconnecting
T, removal of that set isn't a x,y separation.

If x,y are incomparabled, that set is the
lower set of inf{x,y} which includes r.
Removal of that set disconnects T, leaving
x in one part, y in another, a separation.

Apparently, the definition applies
only to incomparable vertices.