Hi,
I tried to "View Postcript" on a file today and LyX just aborted.
However, when I exported the file as LaTeX and used LaTeX, I had no
problems. I'm therefore attaching two copies of the file:- the first
attachment is a version that worked OK, the second attachment is the
file that caused LyX to abort.
Alastair
--
Alastair Farrugia | e-mail: [EMAIL PROTECTED]
PhD student | snail mail: Dept. of Combinatorics, Faculty of
Maths
MC 6101 x6655 | University of Waterloo, Waterloo ON
home: 519-885-7122 | Canada N2L 3G1
#This file was created by <afarrugi> Mon Feb 28 01:35:44 2000
#LyX 1.0 (C) 1995-1999 Matthias Ettrich and the LyX Team
\lyxformat 2.15
\textclass article
\language default
\inputencoding default
\fontscheme default
\graphics default
\paperfontsize default
\spacing single
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default
\layout Standard
\align center
Topological Graph Theory
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
C&0 749 Z
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
Winter 2000
\newline
\layout Standard
\align right
\bar under
Assignment 2
\bar default
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
Alastair Farrugia ID: 99803095
\newline
\layout Description
Definitions.
A
\emph on
branch-decomposition
\emph default
\begin_inset Formula \( (T,z) \)
\end_inset
of a graph
\begin_inset Formula \( G \)
\end_inset
consists of a tree
\begin_inset Formula \( T \)
\end_inset
in which every vertex has degree
\begin_inset Formula \( 3 \)
\end_inset
or
\begin_inset Formula \( 1; \)
\end_inset
and a 1-1 function
\begin_inset Formula \( z \)
\end_inset
from the edges of
\begin_inset Formula \( G \)
\end_inset
to the leaves of
\begin_inset Formula \( T \)
\end_inset
.
(That is, each edge of
\begin_inset Formula \( G \)
\end_inset
is assigned to a unique leaf, and each leaf is assigned either
\begin_inset Formula \( \emptyset \)
\end_inset
or a unique edge of
\begin_inset Formula \( G \)
\end_inset
).
For any two edges
\begin_inset Formula \( e,f \)
\end_inset
of
\begin_inset Formula \( T, \)
\end_inset
we define
\layout Standard
\align left
\begin_inset Formula \( A=A_{e,f} \)
\end_inset
to be the set of edges of
\begin_inset Formula \( G \)
\end_inset
in the component of
\begin_inset Formula \( T-\{e,f\} \)
\end_inset
incident only to
\begin_inset Formula \( e \)
\end_inset
\layout Standard
\align left
\begin_inset Formula \( C=C_{e,f} \)
\end_inset
to be the set of edges of
\begin_inset Formula \( G \)
\end_inset
in the component of
\begin_inset Formula \( T-\{e,f\} \)
\end_inset
incident to both
\begin_inset Formula \( e \)
\end_inset
and
\begin_inset Formula \( f \)
\end_inset
\layout Standard
\align left
\begin_inset Formula \( B=B_{e,f} \)
\end_inset
to be the set of edges of
\begin_inset Formula \( G \)
\end_inset
in the component of
\begin_inset Formula \( T-\{e,f\} \)
\end_inset
incident only to
\begin_inset Formula \( f \)
\end_inset
\layout Standard
\align left
\begin_inset Formula \( P=P_{e,f} \)
\end_inset
to be the unique path in
\begin_inset Formula \( T \)
\end_inset
starting with
\begin_inset Formula \( e \)
\end_inset
and ending with
\begin_inset Formula \( f \)
\end_inset
\layout Standard
\align left
\begin_inset Formula \( \lambda (A,B)=\lambda _{e,f}(A,B) \)
\end_inset
to be the maximum number of vertex disjoint paths
\begin_inset Quotes eld
\end_inset
from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
\begin_inset Quotes erd
\end_inset
.
(That is, the maximum number of vertex-disjoint paths with one end-vertex
incident to an edge in
\begin_inset Formula \( A \)
\end_inset
, the other incident to an edge in
\begin_inset Formula \( B \)
\end_inset
.
Note: if some edge of
\begin_inset Formula \( A \)
\end_inset
is incident to an edge of
\begin_inset Formula \( B \)
\end_inset
, then the common end-vertex will be a trivial path from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
).
\layout Standard
\align left
\begin_inset Formula \( \lambda _{e} \)
\end_inset
is defined to be
\begin_inset Formula \( \lambda _{e,e}(A,B) \)
\end_inset
, for each edge
\begin_inset Formula \( e\in T \)
\end_inset
(Note: In this case we have
\begin_inset Formula \( C_{e,e}=\emptyset \)
\end_inset
,
\begin_inset Formula \( P_{e,e}=e \)
\end_inset
and
\begin_inset Formula \( B_{e,e}=E(G)\setminus A_{e,e} \)
\end_inset
, so
\begin_inset Formula \( \lambda _{e} \)
\end_inset
can also be defined as the number of vertices incident with an edge in
\begin_inset Formula \( A_{e,e} \)
\end_inset
and an edge not in
\begin_inset Formula \( A_{e,e} \)
\end_inset
.
To prove this, we note that these vertices form an
\begin_inset Formula \( (A,B) \)
\end_inset
-cut, so by Menger's Theorem their number is equal to the maximum number
of vertex disjoint paths from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
; but each of these vertices
\emph on
is
\emph default
a path from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
).
\layout Standard
\align left
So, in this form, we can extend the definition to any set of edges of
\begin_inset Formula \( G \)
\end_inset
.
\newline
\protected_separator
\layout Standard
\align left
By Menger's Theorem, for any two edges
\begin_inset Formula \( e,f\in E(T) \)
\end_inset
, and any edge
\begin_inset Formula \( g\in P_{e,f} \)
\end_inset
,
\begin_inset Formula
\[
\lambda _{g}\leq \lambda _{e,f}(A,B)\]
\end_inset
\layout Standard
\align left
If this inequality is sharp for all
\begin_inset Formula \( e,f \)
\end_inset
, then we say that
\begin_inset Formula \( (T,z) \)
\end_inset
is a
\emph on
linked
\emph default
branch decomposition.
\newline
The
\emph on
width
\emph default
of a branch decomposition is
\begin_inset Formula \( \max \{\lambda _{e}|e\in E(T)\} \)
\end_inset
, and the
\emph on
branch width
\emph default
of
\begin_inset Formula \( G \)
\end_inset
is the minimum width over all branch decompositions.
\layout Standard
\align left
\protected_separator
\layout Standard
\align left
\series bold
Theorem.
\series default
Every graph
\begin_inset Formula \( G \)
\end_inset
has a linked branch decomposition
\begin_inset Formula \( (T,z) \)
\end_inset
such that the width of
\begin_inset Formula \( (T,z) \)
\end_inset
is the branch width of
\begin_inset Formula \( G \)
\end_inset
.
\layout Description
Proof:
\protected_separator
(a) Let
\begin_inset Formula \( \cal B \)
\end_inset
be the set of branch decompositions of
\begin_inset Formula \( G \)
\end_inset
having width
\begin_inset Formula \( b \)
\end_inset
, the branch width of
\begin_inset Formula \( G \)
\end_inset
.
For each
\begin_inset Formula \( (T,z)\in \cal B \)
\end_inset
, and each
\begin_inset Formula \( i=0,1,\ldots ,b \)
\end_inset
:
\newline
let
\begin_inset Formula \( T_{i} \)
\end_inset
be the subgraph of
\begin_inset Formula \( T \)
\end_inset
induced by the edges of
\begin_inset Formula \( T \)
\end_inset
with label at least
\begin_inset Formula \( i \)
\end_inset
\newline
let
\begin_inset Formula \( n_{i} \)
\end_inset
and
\begin_inset Formula \( c_{i} \)
\end_inset
denote the number of edges and the number of components, respectively,
of
\begin_inset Formula \( T_{i} \)
\end_inset
\newline
let
\begin_inset Formula \( \sum (T,z) \)
\end_inset
denote the sequence of
\begin_inset Formula \( n_{b},n_{b}-c_{b,}n_{b-1,}n_{b-1}-c_{b-1},\ldots
,n_{1,}n_{1}-c_{1,}n_{0,}n_{0}-c_{0} \)
\end_inset
.
\newline
We shall prove that if
\begin_inset Formula \( (T,z)\in \cal B \)
\end_inset
is not linked, then there is a
\begin_inset Formula \( (T',z')\in \cal B \)
\end_inset
such that
\begin_inset Formula \( \sum (T',z') \)
\end_inset
is lexicographically smaller than
\begin_inset Formula \( \sum (T,z) \)
\end_inset
.
Therefore a decomposition with lexicographically minimal
\begin_inset Formula \( \sum \)
\end_inset
must be linked.
\layout Description
(b) If
\begin_inset Formula \( (T,z) \)
\end_inset
is not linked, then by definition there exist
\begin_inset Formula \( e,f\in E(T) \)
\end_inset
such that
\begin_inset Formula \( \lambda (A,B)<\min \{\lambda _{g}|g\in E(P)\} \)
\end_inset
.
\layout Description
(c) Let
\begin_inset Formula \( V_{A,}V_{B} \)
\end_inset
be the set of end-vertices of edges in
\begin_inset Formula \( A \)
\end_inset
and
\begin_inset Formula \( B \)
\end_inset
, respectively.
By Menger's Theorem there is a
\begin_inset Formula \( (V_{A},V_{B}) \)
\end_inset
-separating cut
\begin_inset Formula \( S \)
\end_inset
with exactly
\begin_inset Formula \( \lambda (A,B) \)
\end_inset
vertices (see Diestel,
\emph on
Graph Theory
\emph default
, Electronic Edition 2000, p.
50).
That is, every path which intersects
\begin_inset Formula \( V_{A} \)
\end_inset
and
\begin_inset Formula \( V_{B} \)
\end_inset
must also intersect
\begin_inset Formula \( S \)
\end_inset
.
\newline
Then, in
\begin_inset Formula \( G\setminus S \)
\end_inset
, no component contains edges from both
\begin_inset Formula \( A \)
\end_inset
and
\begin_inset Formula \( B \)
\end_inset
.
And (in
\begin_inset Formula \( G \)
\end_inset
) no edge of
\begin_inset Formula \( A \)
\end_inset
is incident to a component (of
\begin_inset Formula \( G\setminus S \)
\end_inset
) containing edges of
\begin_inset Formula \( B \)
\end_inset
.
\newline
Note that every edge of
\begin_inset Formula \( G \)
\end_inset
is either in a component of
\begin_inset Formula \( G\setminus S \)
\end_inset
, or is incident to a unique component (it cannot be incident to two components
of
\begin_inset Formula \( G\setminus S \)
\end_inset
), or joins two vertices of
\begin_inset Formula \( S \)
\end_inset
.
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
Let
\begin_inset Formula \( X:=\{e\in E(G)|e\in A \)
\end_inset
, or
\begin_inset Formula \( e \)
\end_inset
is in a component of
\begin_inset Formula \( G\setminus S \)
\end_inset
which contains edges of
\begin_inset Formula \( A \)
\end_inset
, or is incident to such a component
\begin_inset Formula \( \} \)
\end_inset
.
\newline
\begin_inset Formula \( X \)
\end_inset
is intuitively the set of edges on the
\begin_inset Formula \( A \)
\end_inset
side of a smallest vertex-cut separating
\begin_inset Formula \( A \)
\end_inset
from
\begin_inset Formula \( B \)
\end_inset
.
Then it is easy to see that
\begin_inset Formula \( A\subseteq X\subseteq E(G)\setminus B \)
\end_inset
.
It can also be checked that the vertices common to
\begin_inset Formula \( X \)
\end_inset
and
\begin_inset Formula \( E(G)\setminus X \)
\end_inset
are precisely
\begin_inset Formula \( S \)
\end_inset
:
\newline
To show inclusion, we note that an edge in one of the specified components
cannot be incident to any edge not in
\begin_inset Formula \( X \)
\end_inset
(because we defined all the edges incident to those components to be in
\begin_inset Formula \( X \)
\end_inset
too); similarly any edge incident to one of the specified components can
only meet an edge not in
\begin_inset Formula \( X \)
\end_inset
at the
\begin_inset Quotes eld
\end_inset
\begin_inset Formula \( S \)
\end_inset
end-vertex
\begin_inset Quotes erd
\end_inset
; and any other edge in
\begin_inset Formula \( X \)
\end_inset
has both its end-vertices in
\begin_inset Formula \( S \)
\end_inset
anyway.
Now if
\begin_inset Formula \( v\in S \)
\end_inset
is not incident to any edge of
\begin_inset Formula \( X \)
\end_inset
(or not incident to any vertex not in
\begin_inset Formula \( X \)
\end_inset
), it can be seen that there are no paths from
\begin_inset Formula \( V_{A} \)
\end_inset
to
\begin_inset Formula \( V_{B} \)
\end_inset
in
\begin_inset Formula \( G\setminus (S\setminus \{v\}) \)
\end_inset
, so that
\begin_inset Formula \( S \)
\end_inset
is not minimal, which is impossible.
\newline
Of all the possible sets
\begin_inset Formula \( X \)
\end_inset
, we choose the one that crosses as few of the tree partitions as possible.
Here a tree-partition is a partition
\begin_inset Formula \( (A_{e,e},B_{e,e}) \)
\end_inset
of the edge-set of
\begin_inset Formula \( G \)
\end_inset
, corresponding to some edge
\begin_inset Formula \( e\in T. \)
\end_inset
And two partitions
\begin_inset Formula \( (P,Q) \)
\end_inset
,
\begin_inset Formula \( (R,S) \)
\end_inset
are said to cross if none of
\begin_inset Formula \( P\cap R \)
\end_inset
,
\begin_inset Formula \( P\cap S \)
\end_inset
,
\begin_inset Formula \( Q\cap R \)
\end_inset
,
\begin_inset Formula \( Q\cap S \)
\end_inset
is empty.
\layout Description
(d)
\begin_inset Formula \( T \)
\end_inset
can be thought of as
\begin_inset Formula \( A_{e,f}-e-C_{e,f}-f-B_{e,f} \)
\end_inset
.
We create a new branch decomposition
\begin_inset Formula \( (T',z') \)
\end_inset
of
\begin_inset Formula \( G \)
\end_inset
where
\begin_inset Formula \( T' \)
\end_inset
is
\begin_inset Formula \( A_{e,f}-e-C^{e}_{e,f}-a-C^{f}_{e,f}-f-B_{e,f} \)
\end_inset
, or just
\begin_inset Formula \( A-e-C^{e}-a-C^{f}-f-B \)
\end_inset
, where
\begin_inset Formula \( C^{e} \)
\end_inset
and
\begin_inset Formula \( C^{f} \)
\end_inset
are copies of
\begin_inset Formula \( C_{e,e} \)
\end_inset
(the notation is slightly different from that used in the notes).
The assignment of edges to leaves is the same for
\begin_inset Formula \( A \)
\end_inset
and
\begin_inset Formula \( B \)
\end_inset
as it was in
\begin_inset Formula \( T \)
\end_inset
.
But an edge assigned to
\begin_inset Formula \( C \)
\end_inset
in
\begin_inset Formula \( T \)
\end_inset
is now assigned to the corresponding leaf of
\begin_inset Formula \( C^{e} \)
\end_inset
if the edge is in
\begin_inset Formula \( X, \)
\end_inset
and to the leaf of
\begin_inset Formula \( C^{f} \)
\end_inset
otherwise.
\newline
(i) For any edge
\begin_inset Formula \( e'\in E(T') \)
\end_inset
, it is easy to see that if
\begin_inset Formula \( e' \)
\end_inset
is in
\begin_inset Formula \( A\cup \{e\} \)
\end_inset
then
\begin_inset Formula \( A_{e',e'} \)
\end_inset
is the same in
\begin_inset Formula \( T \)
\end_inset
and in
\begin_inset Formula \( T'; \)
\end_inset
while for
\begin_inset Formula \( g \)
\end_inset
in
\begin_inset Formula \( \{f\}\cup B \)
\end_inset
,
\begin_inset Formula \( B_{e',e'} \)
\end_inset
is the same (actually, either condition implies the other).
Thus
\begin_inset Formula \( \lambda _{e'} \)
\end_inset
is unchanged too.
\newline
(ii) Now let
\begin_inset Formula \( e' \)
\end_inset
be in
\begin_inset Formula \( C^{e}\cup \{a\}\cup C^{f} \)
\end_inset
.
We consider first what happens if
\begin_inset Formula \( e'\in E(P_{e,f}) \)
\end_inset
.
We denote
\begin_inset Formula \( A_{e',e'} \)
\end_inset
by
\begin_inset Formula \( A' \)
\end_inset
.
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
Then in
\begin_inset Formula \( T' \)
\end_inset
we have the following situation:
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
(iii) If
\begin_inset Formula \( e'\not \in E(P_{e,f}) \)
\end_inset
, then the picture in
\begin_inset Formula \( T \)
\end_inset
looks like this:
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
while in
\begin_inset Formula \( T' \)
\end_inset
we have:
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\layout Description
(e) The copy of
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( C^{e} \)
\end_inset
always has label
\begin_inset Formula \( \lambda (A'\cap X) \)
\end_inset
.
Now, by submodularity, we have
\begin_inset Formula
\[
\lambda (A'\cap X)+\lambda (A'\cup X)\leq \lambda (A')+\lambda (X)\]
\end_inset
But
\begin_inset Formula \( A\subseteq X\subseteq A'\cup X\subseteq E(G)\setminus
B\Rightarrow \lambda (A'\cup X)\geq \lambda (X) \)
\end_inset
, because
\begin_inset Formula \( X \)
\end_inset
is a minimal
\begin_inset Formula \( A,B \)
\end_inset
-separating set.
So
\begin_inset Formula
\[
\lambda (A'\cap X)+\lambda (X)\leq \lambda (A'\cap X)+\lambda (A'\cup X)\leq \lambda
(A')+\lambda (X)\Rightarrow \lambda (A'\cap X)\leq \lambda (A')\]
\end_inset
So the label on the copy of
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( C^{e} \)
\end_inset
is no larger than the original label of
\begin_inset Formula \( e' \)
\end_inset
.
\newline
If
\begin_inset Formula \( e'\in E(P) \)
\end_inset
, then the copy of
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( C^{f} \)
\end_inset
has label
\begin_inset Formula \( \lambda (\overline{A'}\cap \overline{X}) \)
\end_inset
, so an analogous argument shows that even this copy has label no larger
than
\begin_inset Formula \( \lambda (\overline{A})=\lambda (A) \)
\end_inset
.
\newline
If
\begin_inset Formula \( e'\not \in E(P) \)
\end_inset
, then
\newline
So the label on each edge does not increase; in particular
\begin_inset Formula \( n_{b}\geq {n'}_{b} \)
\end_inset
, and the width of
\begin_inset Formula \( (T',z') \)
\end_inset
is
\begin_inset Formula \( b \)
\end_inset
.
\layout Description
(f) Now suppose the label on the copy of
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( C^{e} \)
\end_inset
is the same as the original label, that is
\begin_inset Formula \( \lambda (A'\cap X)=\lambda (A') \)
\end_inset
.
Then, by the previous equation, we have
\begin_inset Formula \( \lambda (X)\leq \lambda (A'\cup X)\leq \lambda (X) \)
\end_inset
.
So if
\begin_inset Formula \( e'\in E(P) \)
\end_inset
we know that the label on the copy of
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( C^{f} \)
\end_inset
is exactly
\begin_inset Formula \( \lambda (X) \)
\end_inset
.
\layout Description
(g) Suppose we have
\begin_inset Formula \( \lambda (A'\cap X)=\lambda (A') \)
\end_inset
, but now
\begin_inset Formula \( e'\not \in E(P) \)
\end_inset
.
Then .
\newline
So we have shown that for any edge
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( T \)
\end_inset
with label
\begin_inset Formula \( \lambda (A') \)
\end_inset
, we either get
\newline
(i) a single edge in
\begin_inset Formula \( T' \)
\end_inset
labelled
\begin_inset Formula \( \lambda (A') \)
\end_inset
(if
\begin_inset Formula \( e' \)
\end_inset
is in
\begin_inset Formula \( A \)
\end_inset
or
\begin_inset Formula \( B \)
\end_inset
),
\newline
(ii) one edge labelled
\begin_inset Formula \( \lambda (A') \)
\end_inset
and one labelled at most
\begin_inset Formula \( \lambda (X) \)
\end_inset
, or
\newline
(iii) two edges in
\begin_inset Formula \( T' \)
\end_inset
whose labels are both strictly less than
\begin_inset Formula \( \lambda (A') \)
\end_inset
.
\layout Description
(h,
\protected_separator
i) We want to show that
\begin_inset Formula \( \sum (T,z)=n_{b},n_{b}-c_{b,}n_{b-1,}n_{b-1}-c_{b-1},\ldots
,n_{1,}n_{1}-c_{1,}n_{0,}n_{0}-c_{0} \)
\end_inset
is lexicographically larger than
\begin_inset Formula \( \sum
(T',z')={n'}_{b},{n'}_{b}-{c'}_{b,}{n'}_{b-1,}{n'}_{b-1}-{c'}_{b-1},\ldots
,{n'}_{1,}{n'}_{1}-{c'}_{1,}{n'}_{0,}{n'}_{0}-{c'}_{0} \)
\end_inset
.
\layout Description
Case
\protected_separator
1: All the terms are equal up to (but not including) some
\begin_inset Formula \( n_{i} \)
\end_inset
,
\begin_inset Formula \( i>\lambda (X) \)
\end_inset
.
\newline
If
\begin_inset Formula \( i=b \)
\end_inset
, then by (e) we must have
\begin_inset Formula \( n_{b}>{n'}_{b} \)
\end_inset
, so we are done.
Otherwise, in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
we have exactly
\begin_inset Formula \( n_{b} \)
\end_inset
edges labelled
\begin_inset Formula \( b \)
\end_inset
; so case (g)(iii) cannot occur for label
\begin_inset Formula \( b \)
\end_inset
, and thus each edge in
\begin_inset Formula \( T_{i} \)
\end_inset
labelled
\begin_inset Formula \( b \)
\end_inset
gives rise in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
only to edges labelled
\begin_inset Formula \( b \)
\end_inset
[it may give rise to other edges with label at most
\begin_inset Formula \( \lambda (X) \)
\end_inset
, but these will not be in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
].
Then in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
all edges labelled
\begin_inset Formula \( b-1 \)
\end_inset
must come from edges labelled
\begin_inset Formula \( b-1 \)
\end_inset
in
\begin_inset Formula \( T \)
\end_inset
; and since there are exactly
\begin_inset Formula \( {n'}_{b-1}-{n'}_{b}=n_{b-1}-n_{b} \)
\end_inset
such edges, case (g)(iii) cannot occur for label
\begin_inset Formula \( b-1 \)
\end_inset
, so each edge in
\begin_inset Formula \( T_{i} \)
\end_inset
labelled
\begin_inset Formula \( b-1 \)
\end_inset
gives rise in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
only to edges labelled
\begin_inset Formula \( b-1 \)
\end_inset
.
\newline
Continuing in this manner we see that the number of edges of each label
\begin_inset Formula \( b,b-1,\ldots ,i+1 \)
\end_inset
is the same in
\begin_inset Formula \( T_{i} \)
\end_inset
and
\begin_inset Formula \( {T'}_{i} \)
\end_inset
; and the edges labelled
\begin_inset Formula \( i \)
\end_inset
in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
must come from edges labelled
\begin_inset Formula \( i \)
\end_inset
in
\begin_inset Formula \( T_{i} \)
\end_inset
.
But then number of such edges cannot be larger in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
than in
\begin_inset Formula \( T_{i} \)
\end_inset
, so it must be smaller, and we have
\begin_inset Formula \( n_{i}>{n'}_{i} \)
\end_inset
.
\layout Description
Case
\protected_separator
2: All the terms are equal up to (but not including) some
\begin_inset Formula \( n_{i}-c_{i} \)
\end_inset
,
\begin_inset Formula \( i>\lambda (X) \)
\end_inset
.
\newline
So in
\begin_inset Formula \( T_{i} \)
\end_inset
and
\begin_inset Formula \( {T'}_{i} \)
\end_inset
there are the same number of edges of each label
\begin_inset Formula \( b,b-1,\ldots ,i \)
\end_inset
.
And so, by the arguments for Case 1, each edge in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
corresponds to an edge in
\begin_inset Formula \( T_{i} \)
\end_inset
with the same label.
But two edges which are not adjacent in
\begin_inset Formula \( T_{i} \)
\end_inset
will not be adjacent in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
either, as all the edges separating them from each other in
\begin_inset Formula \( T_{i} \)
\end_inset
will still be there in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
(and there might even be new edges inserted in between).
Thus, components of
\begin_inset Formula \( T_{i} \)
\end_inset
are unions of components of
\begin_inset Formula \( {T'}_{i} \)
\end_inset
, and so
\begin_inset Formula \( c_{i}\leq {c'}_{i} \)
\end_inset
.
Since we have inequality in the
\begin_inset Formula \( n_{i}-c_{i} \)
\end_inset
term, it must be
\begin_inset Formula \( n_{i}-c_{i}>{n'}_{i}-{c'}_{i} \)
\end_inset
.
\layout Description
Case
\protected_separator
3: All the terms are equal at least up to
\begin_inset Formula \( n_{\lambda (X)} \)
\end_inset
.
\newline
We will show that this is impossible.
For in
\begin_inset Formula \( T_{i} \)
\end_inset
all edges on the path from
\begin_inset Formula \( e \)
\end_inset
to
\begin_inset Formula \( f \)
\end_inset
had label at least
\begin_inset Formula \( \lambda (X)+1 \)
\end_inset
, so they were all in the same component of
\begin_inset Formula \( T_{\lambda (X)+1} \)
\end_inset
.
Now, these edges cannot all have mapped to
\begin_inset Formula \( C^{e} \)
\end_inset
, or all to
\begin_inset Formula \( C^{f} \)
\end_inset
, for then either
\begin_inset Formula \( \lambda _{e} \)
\end_inset
or
\begin_inset Formula \( \lambda _{f} \)
\end_inset
would have been equal to
\begin_inset Formula \( \lambda (X) \)
\end_inset
.
So some edges go to
\begin_inset Formula \( C^{e} \)
\end_inset
and some to
\begin_inset Formula \( C^{f} \)
\end_inset
; and now they cannot be in the same component of
\begin_inset Formula \( {T'}_{\lambda (X)+1} \)
\end_inset
, because the edge
\begin_inset Formula \( a \)
\end_inset
has label
\begin_inset Formula \( \lambda (X) \)
\end_inset
.
So
\begin_inset Formula \( c_{\lambda (X)+1}\leq {c'}_{\lambda (X)+1} \)
\end_inset
.
\layout Description
Note: We only have
\begin_inset Formula \( n_{j}\geq {n'}_{j} \)
\end_inset
and
\begin_inset Formula \( c_{j}\geq {c'}_{j} \)
\end_inset
for
\begin_inset Formula \( j\geq i \)
\end_inset
, where strict inequality first occurs, and not necessarily all the way
up to
\begin_inset Formula \( \lambda (X). \)
\end_inset
\the_end
#This file was created by <afarrugi> Mon Feb 28 13:52:11 2000
#LyX 1.0 (C) 1995-1999 Matthias Ettrich and the LyX Team
\lyxformat 2.15
\textclass article
\language default
\inputencoding default
\fontscheme default
\graphics default
\paperfontsize default
\spacing single
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default
\layout Standard
\align center
Topological Graph Theory
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
C&0 749 Z
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
Winter 2000
\newline
\layout Standard
\align right
\bar under
Assignment 2
\bar default
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
Alastair Farrugia ID: 99803095
\newline
\layout Description
Definitions.
A
\emph on
branch-decomposition
\emph default
\begin_inset Formula \( (T,z) \)
\end_inset
of a graph
\begin_inset Formula \( G \)
\end_inset
consists of a tree
\begin_inset Formula \( T \)
\end_inset
in which every vertex has degree
\begin_inset Formula \( 3 \)
\end_inset
or
\begin_inset Formula \( 1; \)
\end_inset
and a 1-1 function
\begin_inset Formula \( z \)
\end_inset
from the edges of
\begin_inset Formula \( G \)
\end_inset
to the leaves of
\begin_inset Formula \( T \)
\end_inset
.
(That is, each edge of
\begin_inset Formula \( G \)
\end_inset
is assigned to a unique leaf, and each leaf is assigned either
\begin_inset Formula \( \emptyset \)
\end_inset
or a unique edge of
\begin_inset Formula \( G \)
\end_inset
).
For any two edges
\begin_inset Formula \( e,f \)
\end_inset
of
\begin_inset Formula \( T, \)
\end_inset
we define
\layout Standard
\align left
\begin_inset Formula \( A=A_{e,f} \)
\end_inset
to be the set of edges of
\begin_inset Formula \( G \)
\end_inset
in the component of
\begin_inset Formula \( T-\{e,f\} \)
\end_inset
incident only to
\begin_inset Formula \( e \)
\end_inset
\layout Standard
\align left
\begin_inset Formula \( C=C_{e,f} \)
\end_inset
to be the set of edges of
\begin_inset Formula \( G \)
\end_inset
in the component of
\begin_inset Formula \( T-\{e,f\} \)
\end_inset
incident to both
\begin_inset Formula \( e \)
\end_inset
and
\begin_inset Formula \( f \)
\end_inset
\layout Standard
\align left
\begin_inset Formula \( B=B_{e,f} \)
\end_inset
to be the set of edges of
\begin_inset Formula \( G \)
\end_inset
in the component of
\begin_inset Formula \( T-\{e,f\} \)
\end_inset
incident only to
\begin_inset Formula \( f \)
\end_inset
\layout Standard
\align left
\begin_inset Formula \( P=P_{e,f} \)
\end_inset
to be the unique path in
\begin_inset Formula \( T \)
\end_inset
starting with
\begin_inset Formula \( e \)
\end_inset
and ending with
\begin_inset Formula \( f \)
\end_inset
.
\layout Standard
\align left
\begin_inset Formula \( \lambda (A,B)=\lambda _{e,f}(A,B) \)
\end_inset
is defined to be the maximum number of vertex disjoint paths
\begin_inset Quotes eld
\end_inset
from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
\begin_inset Quotes erd
\end_inset
.
(That is, the maximum number of vertex-disjoint paths with one end-vertex
incident to an edge in
\begin_inset Formula \( A \)
\end_inset
, the other incident to an edge in
\begin_inset Formula \( B \)
\end_inset
.
Note: if some edge of
\begin_inset Formula \( A \)
\end_inset
is incident to an edge of
\begin_inset Formula \( B \)
\end_inset
, then the common end-vertex will be a trivial path from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
).
\layout Standard
\align left
\begin_inset Formula \( \lambda _{e} \)
\end_inset
is defined to be
\begin_inset Formula \( \lambda _{e,e}(A,B) \)
\end_inset
, for each edge
\begin_inset Formula \( e\in T \)
\end_inset
.
(Note: In this case we have
\begin_inset Formula \( C_{e,e}=\emptyset \)
\end_inset
,
\begin_inset Formula \( P_{e,e}=e \)
\end_inset
and
\begin_inset Formula \( B_{e,e}=E(G)\setminus A_{e,e} \)
\end_inset
, so
\begin_inset Formula \( \lambda _{e} \)
\end_inset
can also be defined as the number of vertices incident with an edge in
\begin_inset Formula \( A_{e,e} \)
\end_inset
and an edge not in
\begin_inset Formula \( A_{e,e} \)
\end_inset
.
To prove this, we note that these vertices form an
\begin_inset Formula \( (A,B) \)
\end_inset
-cut, so by Menger's Theorem their number is equal to the maximum number
of vertex disjoint paths from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
; but each of these vertices
\emph on
is
\emph default
a path from
\begin_inset Formula \( A \)
\end_inset
to
\begin_inset Formula \( B \)
\end_inset
.
So, in this form, we can extend the definition to any set of edges of
\begin_inset Formula \( G \)
\end_inset
.)
\newline
\protected_separator
\layout Standard
\align left
By Menger's Theorem, for any two edges
\begin_inset Formula \( e,f\in E(T) \)
\end_inset
, and any edge
\begin_inset Formula \( g\in P_{e,f} \)
\end_inset
,
\begin_inset Formula
\[
\lambda _{e,f}(A,B)\leq \lambda _{g.}\]
\end_inset
\layout Standard
\align left
If this inequality is sharp for all
\begin_inset Formula \( e,f \)
\end_inset
, then we say that
\begin_inset Formula \( (T,z) \)
\end_inset
is a
\emph on
linked
\emph default
branch decomposition.
\newline
The
\emph on
width
\emph default
of a branch decomposition is
\begin_inset Formula \( \max \{\lambda _{e}|e\in E(T)\} \)
\end_inset
, and the
\emph on
branch width
\emph default
of
\begin_inset Formula \( G \)
\end_inset
is the minimum width over all its branch decompositions.
\layout Standard
\align left
\protected_separator
\layout Standard
\align left
\series bold
Theorem.
\series default
Every graph
\begin_inset Formula \( G \)
\end_inset
has a linked branch decomposition
\begin_inset Formula \( (T,z) \)
\end_inset
such that the width of
\begin_inset Formula \( (T,z) \)
\end_inset
is the branch width of
\begin_inset Formula \( G \)
\end_inset
.
\layout Description
Proof:
\protected_separator
(a) Let
\begin_inset Formula \( \cal B \)
\end_inset
be the set of branch decompositions of
\begin_inset Formula \( G \)
\end_inset
having width
\begin_inset Formula \( b \)
\end_inset
, the branch width of
\begin_inset Formula \( G \)
\end_inset
.
For each
\begin_inset Formula \( (T,z)\in \cal B \)
\end_inset
, and each
\begin_inset Formula \( i=0,1,\ldots ,b \)
\end_inset
:
\newline
let
\begin_inset Formula \( T_{i} \)
\end_inset
be the subgraph of
\begin_inset Formula \( T \)
\end_inset
induced by the edges of
\begin_inset Formula \( T \)
\end_inset
with label at least
\begin_inset Formula \( i \)
\end_inset
\newline
let
\begin_inset Formula \( n_{i} \)
\end_inset
and
\begin_inset Formula \( c_{i} \)
\end_inset
denote the number of edges and the number of components, respectively,
of
\begin_inset Formula \( T_{i} \)
\end_inset
\newline
let
\begin_inset Formula \( \sum (T,z) \)
\end_inset
denote the sequence of
\begin_inset Formula \( n_{b},n_{b}-c_{b,}n_{b-1,}n_{b-1}-c_{b-1},\ldots
,n_{1,}n_{1}-c_{1,}n_{0,}n_{0}-c_{0} \)
\end_inset
.
\newline
We shall prove that if
\begin_inset Formula \( (T,z)\in \cal B \)
\end_inset
is not linked, then there is a
\begin_inset Formula \( (T',z')\in \cal B \)
\end_inset
such that
\begin_inset Formula \( \sum (T',z') \)
\end_inset
is lexicographically smaller than
\begin_inset Formula \( \sum (T,z) \)
\end_inset
.
Therefore a decomposition with lexicographically minimal
\begin_inset Formula \( \sum \)
\end_inset
must be linked.
\layout Description
(b) If
\begin_inset Formula \( (T,z) \)
\end_inset
is not linked, then by definition there exist
\begin_inset Formula \( e,f\in E(T) \)
\end_inset
such that
\begin_inset Formula \( \lambda (A,B)<\min \{\lambda _{g}|g\in E(P)\} \)
\end_inset
.
\layout Description
(c) Let
\begin_inset Formula \( V_{A,}V_{B} \)
\end_inset
be the set of end-vertices of edges in
\begin_inset Formula \( A \)
\end_inset
and
\begin_inset Formula \( B \)
\end_inset
, respectively.
By Menger's Theorem there is a
\begin_inset Formula \( (V_{A},V_{B}) \)
\end_inset
-separating cut
\begin_inset Formula \( S \)
\end_inset
with exactly
\begin_inset Formula \( \lambda (A,B) \)
\end_inset
vertices (see Diestel,
\emph on
Graph Theory
\emph default
, Electronic Edition 2000, p.
50).
That is, every path from
\begin_inset Formula \( V_{A} \)
\end_inset
to
\begin_inset Formula \( V_{B} \)
\end_inset
must pass through
\begin_inset Formula \( S \)
\end_inset
.
\newline
Then, in
\begin_inset Formula \( G\setminus S \)
\end_inset
, no component contains edges from both
\begin_inset Formula \( A \)
\end_inset
and
\begin_inset Formula \( B \)
\end_inset
.
And (in
\begin_inset Formula \( G \)
\end_inset
) no edge of
\begin_inset Formula \( A \)
\end_inset
is incident to a component (of
\begin_inset Formula \( G\setminus S \)
\end_inset
) containing edges of
\begin_inset Formula \( B \)
\end_inset
.
\newline
Note that every edge of
\begin_inset Formula \( G \)
\end_inset
is either in a component of
\begin_inset Formula \( G\setminus S \)
\end_inset
, or is incident to a unique component (it cannot be incident to two components
of
\begin_inset Formula \( G\setminus S \)
\end_inset
), or joins two vertices of
\begin_inset Formula \( S \)
\end_inset
.
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
\protected_separator
\newline
Let
\begin_inset Formula \( X:=\{e\in E(G)|e\in A \)
\end_inset
, or
\begin_inset Formula \( e \)
\end_inset
is in a component of
\begin_inset Formula \( G\setminus S \)
\end_inset
which contains edges of
\begin_inset Formula \( A \)
\end_inset
, or is incident to such a component
\begin_inset Formula \( \} \)
\end_inset
.
\newline
\begin_inset Formula \( X \)
\end_inset
is intuitively the set of edges in
\begin_inset Formula \( A \)
\end_inset
, or on the
\begin_inset Formula \( A \)
\end_inset
side of a smallest vertex-cut separating
\begin_inset Formula \( A \)
\end_inset
from
\begin_inset Formula \( B \)
\end_inset
.
Then it is easy to see that
\begin_inset Formula \( A\subseteq X\subseteq \overline{B} \)
\end_inset
.
It can also be checked that the vertices common to
\begin_inset Formula \( X \)
\end_inset
and
\begin_inset Formula \( \overline{X} \)
\end_inset
are precisely
\begin_inset Formula \( S \)
\end_inset
:
\newline
To show inclusion, we note that an edge in one of the specified components
cannot be incident to any edge not in
\begin_inset Formula \( X \)
\end_inset
(because we defined all the edges incident to those components to be in
\begin_inset Formula \( X \)
\end_inset
too); similarly any edge incident to one of the specified components can
only meet an edge not in
\begin_inset Formula \( X \)
\end_inset
at the
\begin_inset Quotes eld
\end_inset
\begin_inset Formula \( S \)
\end_inset
end-vertex
\begin_inset Quotes erd
\end_inset
; and any other edge in
\begin_inset Formula \( X \)
\end_inset
has both its end-vertices in
\begin_inset Formula \( S \)
\end_inset
anyway.
To show equality we note that removing the vertices common to
\begin_inset Formula \( X \)
\end_inset
and
\begin_inset Formula \( \overline{X} \)
\end_inset
separates
\begin_inset Formula \( V_{A} \)
\end_inset
from
\begin_inset Formula \( V_{B} \)
\end_inset
; but
\begin_inset Formula \( S \)
\end_inset
is a minimal separating set.
\newline
Of all the possible sets
\begin_inset Formula \( X \)
\end_inset
, we choose the one that crosses as few of the tree partitions as possible.
Here a tree-partition is a partition
\begin_inset Formula \( (A_{e,e},B_{e,e}) \)
\end_inset
of the edge-set of
\begin_inset Formula \( G \)
\end_inset
, corresponding to some edge
\begin_inset Formula \( e\in T. \)
\end_inset
And two partitions
\begin_inset Formula \( (P,Q) \)
\end_inset
,
\begin_inset Formula \( (R,S) \)
\end_inset
are said to cross if none of
\begin_inset Formula \( P\cap R \)
\end_inset
,
\begin_inset Formula \( P\cap S \)
\end_inset
,
\begin_inset Formula \( Q\cap R \)
\end_inset
,
\begin_inset Formula \( Q\cap S \)
\end_inset
is empty.
\layout Description
(d)
\begin_inset Formula \( T \)
\end_inset
can be thought of as
\begin_inset Formula \( A_{e,f}-e-C_{e,f}-f-B_{e,f} \)
\end_inset
.
We create a new branch decomposition
\begin_inset Formula \( (T',z') \)
\end_inset
of
\begin_inset Formula \( G \)
\end_inset
where
\begin_inset Formula \( T' \)
\end_inset
is
\begin_inset Formula \( A_{e,f}-e-C^{e}_{e,f}-a-C^{f}_{e,f}-f-B_{e,f} \)
\end_inset
, or for simplicity just
\begin_inset Formula \( A-e-C^{e}-a-C^{f}-f-B \)
\end_inset
, where
\begin_inset Formula \( C^{e} \)
\end_inset
and
\begin_inset Formula \( C^{f} \)
\end_inset
are copies of
\begin_inset Formula \( C_{e,f} \)
\end_inset
(the notation is slightly different from that used in the notes).
The assignment of edges to leaves is the same for
\begin_inset Formula \( A \)
\end_inset
and
\begin_inset Formula \( B \)
\end_inset
as it was in
\begin_inset Formula \( T \)
\end_inset
.
But an edge assigned to
\begin_inset Formula \( C \)
\end_inset
in
\begin_inset Formula \( T \)
\end_inset
is now assigned to the corresponding leaf of
\begin_inset Formula \( C^{e} \)
\end_inset
if the edge is in
\begin_inset Formula \( X, \)
\end_inset
and to the leaf of
\begin_inset Formula \( C^{f} \)
\end_inset
otherwise.
\newline
(i) For any edge
\begin_inset Formula \( e'\in E(T) \)
\end_inset
, it is easy to see that if
\begin_inset Formula \( e' \)
\end_inset
is in
\begin_inset Formula \( A\cup \{e\} \)
\end_inset
then
\begin_inset Formula \( A_{e',e'} \)
\end_inset
is the same in
\begin_inset Formula \( T \)
\end_inset
and in
\begin_inset Formula \( T'; \)
\end_inset
while for
\begin_inset Formula \( g \)
\end_inset
in
\begin_inset Formula \( \{f\}\cup B \)
\end_inset
,
\begin_inset Formula \( B_{e',e'} \)
\end_inset
is the same (actually, either condition implies the other).
Thus
\begin_inset Formula \( \lambda _{e'} \)
\end_inset
is unchanged for these edges.
\newline
(ii) Now let
\begin_inset Formula \( e' \)
\end_inset
be in
\begin_inset Formula \( C \)
\end_inset
, and consider first what happens if
\begin_inset Formula \( e'\in E(P_{e,f}) \)
\end_inset
.
We denote
\begin_inset Formula \( A_{e',e'} \)
\end_inset
by
\begin_inset Formula \( A' \)
\end_inset
; then we have the situation shown below:
\newline
\protected_separator
\newline
\protected_separator
\layout Standard
\align center
\begin_inset Formula \( A \)
\end_inset
------
\begin_inset Formula \( C_{1} \)
\end_inset
------
\begin_inset Formula \( C_{2} \)
\end_inset
------
\begin_inset Formula \( B \)
\end_inset
\layout Description
.
\protected_separator
\newline
\protected_separator
\newline
while in
\begin_inset Formula \( T' \)
\end_inset
we have the following situation:
\newline
\protected_separator
\newline
\layout Standard
\align center
\begin_inset Formula \( A \)
\end_inset
------
\begin_inset Formula \( C_{1,e} \)
\end_inset
------
\begin_inset Formula \( C_{2,e} \)
\end_inset
------
\begin_inset Formula \( C_{1,f} \)
\end_inset
------
\begin_inset Formula \( C_{2,f} \)
\end_inset
------
\begin_inset Formula \( B \)
\end_inset
\layout Description
.
\protected_separator
\newline
\protected_separator
\newline
Now we have
\begin_inset Formula \( A'=A\cup C_{1} \)
\end_inset
,
\begin_inset Formula \( C_{1,e}=C_{1}\cap X \)
\end_inset
,
\begin_inset Formula \( C_{2,e}=C_{2}\cap X \)
\end_inset
,
\begin_inset Formula \( C_{1,f}=C_{1}\cap \overline{X} \)
\end_inset
,
\begin_inset Formula \( C_{2,e}=C_{2}\cap \overline{X} \)
\end_inset
, and so
\begin_inset Formula
\[
\lambda ({e'}_{e})=\lambda (A\cup C_{1,e})=\lambda (A'\cap X)\]
\end_inset
\begin_inset Formula
\[
\lambda ({e'}_{f})=\lambda (A\cup C_{1,e}\cup C_{2,e}\cup C_{1,f})=\lambda (A'\cup
X).\]
\end_inset
Note that
\begin_inset Formula \( \lambda (A'\cup X)=\lambda (\overline{A'\cup X})=\lambda
(\overline{A'}\cap \overline{X}) \)
\end_inset
.
\layout Description
(iii) If
\begin_inset Formula \( e'\not \in E(P_{e,f}) \)
\end_inset
, then the picture in
\begin_inset Formula \( T \)
\end_inset
looks like this:
\newline
\protected_separator
\newline
\protected_separator
\layout Standard
\align center
\begin_inset Formula \( A \)
\end_inset
------
\begin_inset Formula \( C_{1} \)
\end_inset
------
\begin_inset Formula \( B \)
\end_inset
\newline
|
\newline
\begin_inset Formula \( C_{2} \)
\end_inset
\layout Description
.
\protected_separator
\newline
\protected_separator
\newline
while in
\begin_inset Formula \( T' \)
\end_inset
we have:
\newline
\protected_separator
\newline
\protected_separator
\layout Standard
\align center
\begin_inset Formula \( A \)
\end_inset
------
\begin_inset Formula \( C_{1,e} \)
\end_inset
------
\begin_inset Formula \( C_{1,f} \)
\end_inset
------
\begin_inset Formula \( B \)
\end_inset
\newline
|
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
|
\newline
\begin_inset Formula \( C_{2,e} \)
\end_inset
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\protected_separator
\begin_inset Formula \( C_{2,f} \)
\end_inset
\layout Description
.
\protected_separator
\newline
\protected_separator
\newline
We now have
\begin_inset Formula \( A'=C_{2} \)
\end_inset
,
\begin_inset Formula \( C_{1,e}=C_{1}\cap X \)
\end_inset
,
\begin_inset Formula \( C_{2,e}=C_{2}\cap X \)
\end_inset
,
\begin_inset Formula \( C_{1,f}=C_{1}\cap \overline{X} \)
\end_inset
,
\begin_inset Formula \( C_{2,e}=C_{2}\cap \overline{X} \)
\end_inset
, so
\begin_inset Formula
\[
\lambda ({e'}_{e})=\lambda (C_{2,e})=\lambda (A'\cap X)\]
\end_inset
\begin_inset Formula
\[
\lambda ({e'}_{f})=\lambda (C_{2,f})=\lambda (A'\cap \overline{X})=\lambda
(A'\setminus X).\]
\end_inset
\layout Description
(e) The edge
\begin_inset Formula \( {e'}_{e} \)
\end_inset
always has label
\begin_inset Formula \( \lambda (A'\cap X) \)
\end_inset
.
Now, by submodularity, we have
\begin_inset Formula
\[
\lambda (A'\cap X)+\lambda (A'\cup X)\leq \lambda (A')+\lambda (X)\]
\end_inset
But
\begin_inset Formula \( A\subseteq X\subseteq A'\cup X\subseteq
\overline{B}\Rightarrow \lambda (A'\cup X)\geq \lambda (X) \)
\end_inset
, because
\begin_inset Formula \( X \)
\end_inset
is a minimal
\begin_inset Formula \( A,B \)
\end_inset
-separating set.
So
\begin_inset Formula
\[
\lambda (A'\cap X)+\lambda (X)\leq \lambda (A'\cap X)+\lambda (A'\cup X)\leq \lambda
(A')+\lambda (X)\Rightarrow \lambda (A'\cap X)\leq \lambda (A')\]
\end_inset
So the label on
\begin_inset Formula \( {e'}_{e} \)
\end_inset
is no larger than the original label of
\begin_inset Formula \( e' \)
\end_inset
.
\newline
If
\begin_inset Formula \( e'\in E(P) \)
\end_inset
, then
\begin_inset Formula \( {e'}_{f} \)
\end_inset
has label
\begin_inset Formula \( \lambda (\overline{A'}\cap \overline{X}) \)
\end_inset
, and
\begin_inset Formula \( \overline{A}\supseteq \overline{A'}\cup \overline{X}\supseteq
\overline{X}\supseteq B \)
\end_inset
, so an analogous argument shows that even this copy has label no larger
than
\begin_inset Formula \( \lambda (\overline{A})=\lambda (A) \)
\end_inset
.
\newline
If
\begin_inset Formula \( e'\not \in E(P) \)
\end_inset
, then
\begin_inset Formula \( {e'}_{f} \)
\end_inset
has label
\begin_inset Formula \( \lambda (A'\cap \overline{X}) \)
\end_inset
, and
\begin_inset Formula \( \overline{A}\supseteq A'\cup \overline{X}\supseteq
\overline{X}\supseteq B \)
\end_inset
, so
\begin_inset Formula \( \lambda (A'\cup \overline{X})\geq \lambda (X) \)
\end_inset
.
Then using submodularity we get
\begin_inset Formula
\[
\lambda (A'\cap \overline{X})+\lambda (X)\leq \lambda (A'\cap \overline{X})+\lambda
(A'\cup \overline{X})\leq \lambda (A')+\lambda (\overline{X})\Rightarrow \lambda
(A'\cap \overline{X})\leq \lambda (A')\]
\end_inset
The edge
\begin_inset Formula \( a \)
\end_inset
does not correspond to any edge in
\begin_inset Formula \( T \)
\end_inset
, but we know that
\begin_inset Formula \( \lambda (a)=\lambda (X)<b \)
\end_inset
.
\newline
So the label on each edge does not increase; in particular the width of
\begin_inset Formula \( (T',z') \)
\end_inset
is
\begin_inset Formula \( b \)
\end_inset
, and
\begin_inset Formula \( n_{b}\geq {n'}_{b} \)
\end_inset
.
\layout Description
(f) Now suppose the label on the copy of
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( C^{e} \)
\end_inset
is the same as the original label, that is
\begin_inset Formula \( \lambda (A'\cap X)=\lambda (A') \)
\end_inset
.
Then, by the previous equation, we have
\begin_inset Formula \( \lambda (X)\leq \lambda (A'\cup X)\leq \lambda (X) \)
\end_inset
.
So if
\begin_inset Formula \( e'\in E(P) \)
\end_inset
we know that the label on the copy of
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( C^{f} \)
\end_inset
is exactly
\begin_inset Formula \( \lambda (X) \)
\end_inset
.
\layout Description
(g) Suppose we have
\begin_inset Formula \( \lambda (A'\cap X)=\lambda (A') \)
\end_inset
, but now
\begin_inset Formula \( e'\not \in E(P) \)
\end_inset
.
Then we want to show that
\begin_inset Formula \( \lambda (A'\cap \overline{X})\leq \lambda (X) \)
\end_inset
, or equivalently
\begin_inset Formula \( \lambda (\overline{A'}\cup X)\leq \lambda (X) \)
\end_inset
.
Now the second equation of (e) gives us
\begin_inset Formula \( \lambda (A'\cup X)=\lambda (X) \)
\end_inset
.
If this occurs because
\begin_inset Formula \( A'\cup X=X \)
\end_inset
, then
\begin_inset Formula \( A'\cap \overline{X}=\emptyset \)
\end_inset
, and so
\begin_inset Formula \( \lambda (A'\cup \overline{X})=\lambda (\emptyset )=0\leq
\lambda (X) \)
\end_inset
.
\newline
We will show that the alternative is impossible, as then
\begin_inset Formula \( (A'\cup X,\overline{A'\cup X}) \)
\end_inset
crosses fewer tree-partitions than
\begin_inset Formula \( (X,\overline{X}) \)
\end_inset
, which contradicts the choice of
\begin_inset Formula \( X \)
\end_inset
.
\newline
\newline
\newline
So we have shown that for any edge
\begin_inset Formula \( e' \)
\end_inset
in
\begin_inset Formula \( T \)
\end_inset
with label
\begin_inset Formula \( \lambda (A') \)
\end_inset
, we either get
\newline
(i) a single edge in
\begin_inset Formula \( T' \)
\end_inset
labelled
\begin_inset Formula \( \lambda (A') \)
\end_inset
(if
\begin_inset Formula \( e' \)
\end_inset
is in
\begin_inset Formula \( A \)
\end_inset
or
\begin_inset Formula \( B \)
\end_inset
),
\newline
(ii) one edge labelled
\begin_inset Formula \( \lambda (A') \)
\end_inset
and one labelled at most
\begin_inset Formula \( \lambda (X) \)
\end_inset
, or
\newline
(iii) two edges in
\begin_inset Formula \( T' \)
\end_inset
whose labels are both strictly less than
\begin_inset Formula \( \lambda (A') \)
\end_inset
.
\layout Description
(h,
\protected_separator
i) We want to show that
\begin_inset Formula \( \sum (T,z)=n_{b},n_{b}-c_{b,}n_{b-1,}n_{b-1}-c_{b-1},\ldots
,n_{1,}n_{1}-c_{1,}n_{0,}n_{0}-c_{0} \)
\end_inset
is lexicographically larger than
\begin_inset Formula \( \sum
(T',z')={n'}_{b},{n'}_{b}-{c'}_{b,}{n'}_{b-1,}{n'}_{b-1}-{c'}_{b-1},\ldots
,{n'}_{1,}{n'}_{1}-{c'}_{1,}{n'}_{0,}{n'}_{0}-{c'}_{0} \)
\end_inset
.
\layout Description
Case
\protected_separator
1: All the terms are equal up to (but not including) some
\begin_inset Formula \( n_{i} \)
\end_inset
,
\begin_inset Formula \( i>\lambda (X) \)
\end_inset
.
\newline
If
\begin_inset Formula \( i=b \)
\end_inset
, then by (e) we must have
\begin_inset Formula \( n_{b}>{n'}_{b} \)
\end_inset
, so we are done.
Otherwise, in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
we have exactly
\begin_inset Formula \( n_{b} \)
\end_inset
edges labelled
\begin_inset Formula \( b \)
\end_inset
; so case (g)(iii) cannot occur for label
\begin_inset Formula \( b \)
\end_inset
, and thus each edge in
\begin_inset Formula \( T_{i} \)
\end_inset
labelled
\begin_inset Formula \( b \)
\end_inset
gives rise in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
only to edges labelled
\begin_inset Formula \( b \)
\end_inset
[it may give rise to other edges with label at most
\begin_inset Formula \( \lambda (X) \)
\end_inset
, but these will not be in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
].
Then in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
all edges labelled
\begin_inset Formula \( b-1 \)
\end_inset
must come from edges labelled
\begin_inset Formula \( b-1 \)
\end_inset
in
\begin_inset Formula \( T \)
\end_inset
; and since there are exactly
\begin_inset Formula \( {n'}_{b-1}-{n'}_{b}=n_{b-1}-n_{b} \)
\end_inset
such edges, case (g)(iii) cannot occur for label
\begin_inset Formula \( b-1 \)
\end_inset
, so each edge in
\begin_inset Formula \( T_{i} \)
\end_inset
labelled
\begin_inset Formula \( b-1 \)
\end_inset
gives rise in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
only to edges labelled
\begin_inset Formula \( b-1 \)
\end_inset
.
\newline
Continuing in this manner we see that the number of edges of each label
\begin_inset Formula \( b,b-1,\ldots ,i+1 \)
\end_inset
is the same in
\begin_inset Formula \( T_{i} \)
\end_inset
and
\begin_inset Formula \( {T'}_{i} \)
\end_inset
; and the edges labelled
\begin_inset Formula \( i \)
\end_inset
in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
must come from edges labelled
\begin_inset Formula \( i \)
\end_inset
in
\begin_inset Formula \( T_{i} \)
\end_inset
.
But then number of such edges cannot be larger in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
than in
\begin_inset Formula \( T_{i} \)
\end_inset
, so it must be smaller, and we have
\begin_inset Formula \( n_{i}>{n'}_{i} \)
\end_inset
.
\layout Description
Case
\protected_separator
2: All the terms are equal up to (but not including) some
\begin_inset Formula \( n_{i}-c_{i} \)
\end_inset
,
\begin_inset Formula \( i>\lambda (X) \)
\end_inset
.
\newline
So in
\begin_inset Formula \( T_{i} \)
\end_inset
and
\begin_inset Formula \( {T'}_{i} \)
\end_inset
there are the same number of edges of each label
\begin_inset Formula \( b,b-1,\ldots ,i \)
\end_inset
.
And so, by the arguments for Case 1, each edge in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
corresponds to an edge in
\begin_inset Formula \( T_{i} \)
\end_inset
with the same label.
But two edges which are not adjacent in
\begin_inset Formula \( T_{i} \)
\end_inset
will not be adjacent in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
either, as all the edges separating them from each other in
\begin_inset Formula \( T_{i} \)
\end_inset
will still be there in
\begin_inset Formula \( {T'}_{i} \)
\end_inset
(and there might even be new edges inserted in between).
Thus, components of
\begin_inset Formula \( T_{i} \)
\end_inset
are unions of components of
\begin_inset Formula \( {T'}_{i} \)
\end_inset
, and so
\begin_inset Formula \( c_{i}\leq {c'}_{i} \)
\end_inset
.
Since we have inequality in the
\begin_inset Formula \( n_{i}-c_{i} \)
\end_inset
term, it must be
\begin_inset Formula \( n_{i}-c_{i}>{n'}_{i}-{c'}_{i} \)
\end_inset
.
\layout Description
Case
\protected_separator
3: All the terms are equal at least up to
\begin_inset Formula \( n_{\lambda (X)} \)
\end_inset
.
\newline
We will show that this is impossible.
For in
\begin_inset Formula \( T_{i} \)
\end_inset
all edges on the path from
\begin_inset Formula \( e \)
\end_inset
to
\begin_inset Formula \( f \)
\end_inset
had label at least
\begin_inset Formula \( \lambda (X)+1 \)
\end_inset
, so they were all in the same component of
\begin_inset Formula \( T_{\lambda (X)+1} \)
\end_inset
.
Now, these edges cannot all have mapped to
\begin_inset Formula \( C^{e} \)
\end_inset
, or all to
\begin_inset Formula \( C^{f} \)
\end_inset
, for then either
\begin_inset Formula \( \lambda _{e} \)
\end_inset
or
\begin_inset Formula \( \lambda _{f} \)
\end_inset
would have been equal to
\begin_inset Formula \( \lambda (X) \)
\end_inset
.
So some edges go to
\begin_inset Formula \( C^{e} \)
\end_inset
and some to
\begin_inset Formula \( C^{f} \)
\end_inset
; and now they cannot be in the same component of
\begin_inset Formula \( {T'}_{\lambda (X)+1} \)
\end_inset
, because the edge
\begin_inset Formula \( a \)
\end_inset
has label
\begin_inset Formula \( \lambda (X) \)
\end_inset
.
So
\begin_inset Formula \( c_{\lambda (X)+1}\leq {c'}_{\lambda (X)+1} \)
\end_inset
.
\layout Description
Note: We only have
\begin_inset Formula \( n_{j}\geq {n'}_{j} \)
\end_inset
and
\begin_inset Formula \( c_{j}\geq {c'}_{j} \)
\end_inset
for
\begin_inset Formula \( j\geq i \)
\end_inset
, where strict inequality first occurs, and not necessarily all the way
up to
\begin_inset Formula \( \lambda (X). \)
\end_inset
\the_end
