#

Solutions Manual of Elements of Discrete Mathematics

CHAPTER

FIVE
TREES AND CUT-SETS
5.1 Exactly two vertices have degree 1, all others have degree 2. Thus, the
graph looks like

5.2 There are 2n + 3n + n = 6n vertices, and hence 6n 1 edges. Thus

Hence

2(6n 1) = 1(2n) + 2(3n) + 3(n)

n = 2, and there are 12 vertices and 11 edges.

5.3 (a) 9
(b) Let e denote the number of edges in the tree.
Also,

2e = n1 + 2n2 + 3n3 + + knk

2e = 2(v 1) = 2(n1 + n2 + n3 + + n k 1)
n1 = n3 + 2n4 + + (k 2)nk + 2

5.4 n1 + n2 = 51
Thus

n1 = e2 = n2 1
n1 = 25, e1 = 24, and n2 = 26, e2 = 25.

T1 has 25 vertices 24 edges, while T2 has 26 vertices and 25 edges.

5.5 (a) There are v 1 edges.
(b) v = 2,
v=3

d1 = d2 = 1
(2, 1, 1)

#

Trees and Cut-sets

v -1

di

Assume for n = v 1,

= 2(v 1) 2 yields a tree. Let

i =1

(d1, d2,, dv) be an ordered v-tuples such that

= 2v 2. There

i =1

exists i such that di = 1. If not,

dj > 1.

2 v . There exists j such that

eIf not, d = v < 2 v - 2 for v > 2j .

i

We can remove di,

change dj to dj 1 and apply the induction hypothesis.

5.6 (a)

(b)K4

5.6 (a)
(c) We define the eccentricity e(v) of a vertex v in a connected graph G to
be max d(u, v) for all u in G. Let T be a tree. Let T be a tree obtained
from T by removing all leaves of T. Clearly, the eccentricity of each
vertex of T is exactly one less than the eccentricity of the same vertex
of T. Hence, the vertices of T which possess minimum eccentricity in
T are the same vertices having minimum eccentricity in T . Then is, T
and T have the same center. Repeating the argument, we shall
terminate either at a tree that is single vertex or at a tree that has one
edge and two vertices.
10

5.7 (a)

10

10

5.7 (a)

10

10

10

(b)

(b)

C1

C2

Solutions Manual of Elements of Discrete Mathematics

(c) Let v be a centroid. Let v1, v2,, vk and s1, s2,, sk be as defined. Let
T1, T2,, Tk denote the subtrees with v1, v2,, vk as roots. Clearly,
the weight of v1 is at least n s1 = 1 + s2 + s3 + + sk where n is the
number of vertices in the tree, since the subtree with v as the root has
n s1 vertices. If there is a centroid, y1, in subtree T1, then wt(y1) n
s1 = 1 + s2 + s3 + + sk and wt(y1) = wt(v) = max (s1, s2,, sk) 1
+ s2 + + sk and this implies s1 > s2 + + sk. A similar argument can
be applied to other subtrees T2, T3,, Tk. Therefore, at most one of
the subtrees, say Tj, may contain a centroid, vj. Furthermore, Tj is the
heaviest subtree of v, and conversely, the subtree with v as the root is
the heaviest subtree of yj. Thus, if yj is not adjacent to v, then vj must
be on the path from yj to v and it implies wt(yj) wt(v) + 1 which is a
contradiction. Therefore, v and yj must be adjacent.
(d) From (c), it is shown that if there is a centroid in subtree Tj, then sj >
s1 + + sk sj. So, if sj s1 + + sk sj then there is no such centroid
in that subtree. If it is true for 1 j k, then no more centroids exist
besides v.
(e) From c, the two centroids v, yj are of same weight and adjacent to each
other and v is the root of the heaviest subtree of yj and yj is in the root
of the subtree of v. Thus, these two subtrees partition the n vertices in
the tree. It follows that n = wt(v) + wt(yj) = 2 wt(v).
5.8 There is one vertex of degree 2. All other vertices are of degree 3 or 1.
There must be an even number of vertices of degree 3 or 1.
5.9 To show that number of leaves t = (m 1)i + 1.
Basis:

i=0

t = 1 = (m 1) 0 + 1

Induction Step: Given a regular m-ary tree T, with i internal nodes, there
must be one with m leaves as its sons. (Choose an internal
nodes that is furthest from the root.) Remove this internal
node and all its son and replace them with a leaf as shown
below. We have a regular m-ary tree, T , with i 1 internal
nodes. By induction hypothesis, the number of leaves in T
= (m 1) (i 1) + 1. Therefore the number of leaves in T
must be (m 1) (i 1) + 1 + (m 1) = (m 1) i + 1.

#!

Trees and Cut-sets

5.10

abdgehicf
gdbheiacf
gdhiebfca

5.11 Assume A f. We construct a binary tree as follows: Assign A to the root.

Assign A0 to the left son of A, and A1 to the right son of A with the
corresponding branches being 0 and 1, respectively. Such a repeated
partition will yield a binary tree each of its leaves corresponds to a
sequence in A.
5.12 (a) (73 + 44 1) + (73 + 44 + 100 1) + (73 + 44 + 100 + 55 1) = 603
(b) (73 + 44 1) + (100 + 55 1) + (73 + 44 + 100 + 55 1) = 541
(c) Merge A2 and A4, then A1 and A2 A4, and then A3 and A1 A2 A4. Total
number of comparisons = 540.
(d) Construct a Huffman tree with the lengths of A1, A2,, Am as the
weights of the leaves.
5.13 (a)

5.13 (a)
8 = 000 9 = 001 12 = 010 14 = 011 16 = 10 19 = 11

(b)

12 = 10

10 = 00

9 = 111

6 = 011

5 = 010

(b)

4 = 1101

1 = 11000

2 = 11001

(c)
40 = 0
35 = 10

(c)

15 = 110
8 = 1110
5 = 11110

7 = 11111

#"

Solutions Manual of Elements of Discrete Mathematics

5.14 (a) Select the m smallest weights in each step.

(b)

(b)
1

(c) (i)

(c) (i)
0

(ii) Put in dummy weights of value 0.

5.15 Choose K n/2 as the root and construct recursively with the left subtree
containing the keys K1, K2,, K n/2 1 and the right subtree containing the
keys K n/2 +1,, Kn.
5.16 (a) (i) Examine the root. If it has one key then it will have two sons, and
by comparison if it is the key we want we are done. If it is greater,
we search to the left, otherwise to the right. If the root has two
keys then we compare with the first. If it equals the one we want,
we are done; if it is greater, we search the left subtree; if it is less,
we compare with the second key. If equal, we are done; if greater,
we search the center subtree; if less, we search the right subtree.
(ii) Let k denote the number of keys. Let v1 denote the number of
leaves, v2 denote the number of internal nodes with 1 key and v3
denote the number of internal nodes of 2 keys. Let e denote the
number of edges.
(1)
(2)
(3)

k = 2v3 + v2
e = 3v3 + 2v2
e = v3 + v2 + v1 1

From (1), (2), and (3) we obtain k = v1 1.

5.17 A spanning tree has at least one edge in common with every cut-set by
Theorem 5.2. Therefore, the complement of a spanning tree lacks one or
more edges from every cut-set.

##

Trees and Cut-sets

A cut-set has at least one edge in common with every spanning tree,
again by Theorem 5.2. Therefore, the complement of a cut-set lacks one or
more edges of every spanning tree.
5.18 Let T be a spanning tree in G containing all the edges L a. Let C be the
fundamental cut-set, relative to T, corresponding to the tree branch b.
Then,
{L a} C = b
and by Theorem 6.3.
L C = {a, b}
5.19 Let C1 be the fundamental cut-set relative to T1 corresponding to edge a.
C1 T1 = {a}

(1)

Since a T2, a is a chord of T2 and defines a fundamental circuit L

relative to T2.
L T2 = {a}

(2)

Applying Theorem 5.3 L C1 contains an even number of edges, one of

which is a. Let b be any other. Since b L, by (2) b T2. Since b C1, by
(1) b T1, and (T1 {a}) {b} is a spanning tree. Let C2 be the
fundamental cut-set relative to T2 corresponding to edge b.
C2 T2 = {b}

(3)

Applying Theorem 5.3 L C2 contains an even number of edges, one of

which is b. By (3) all other lie in T2. By (2), L C2 = {a, b}. Since a C2,
(T2 {b}) {a} is a spanning tree.
5.20 (a) Let L = L1 L2. Then L L1 L2 and a L, b L.
Thus,

L L1 L2 {a}

and

b L.

Now. L is either a circuit or edge-disjoint union of circuits. If L is a

circuit, let L3 = L. If L is an edge-disjoint union of circuits, let L3 be the
one circuit in L that contains the edge b.
(b) In the solution for part (a), replace circuit with cut-set.
5.21 Exactly as that for Theorems 5.4 except interchange circuit (C) and chord
with cut-set (D) and branch, respectively.
5.22 (a) 4 1 6 4
(b) Whenever an edge is deleted, the degree of the non-leaf vertex is
decreased by 1. So, if this vertex appears i times, its degree is
decreased by i. Finally, this vertex is removed as a leaf or is left as one
of the two connected vertices. Its degree is 1 in either case.

#$

Solutions Manual of Elements of Discrete Mathematics

(c) Let d(i) be the degree of vertex i which can be calculated according to
(b).
(1) set i = 1
(2) Among all vertices whose present degree is 1, find the one, vi,
with the least name. Draw an edge connecting vi to vertex ai.
Eliminate vertex vi from the list and reduce d(ai) by one.
(3) If i < n 2, increase i by 1 and go to step (2). If i = n 2, draw an
edge between the two remaining vertices (of degree 1) and stop.
(d) Clearly, the algorithm always yields a tree. Furthermore, the tree yields
will be the only one which will produce the original number sequence.
5.23 (a) Let T be a spanning tree of G. If edge e is in T, then we are done.
Otherwise, adding e in T will form a cycle. Remove an edge (other
than e) from this cycle will give a tree T containing e.
(b) No. A counter-example is the edge e below

5.24 (a) No. In G1, there is a path from v1 to v2 and in G2 there is a path from
v4 to v3. Thus there is a cycle in G containing v1, v2, v3 and v4.
(b) Given any two vertices u and v, if they both belong to either G1 or G2,
then clearly there is a path from u to v. Otherwise, assume that u is in
G1 and v is in G2. Then there is a path from u to v as follows: First
follow path in G1 from u to v1, then follow edge {v1, v3} and then
follow path in G2 from v3 to v.
(c) G1 is a path with v1 and v2 as its end points. Similarly, G2 is a path with
v3 and v4 as its end points.
5.25 (a)
(b)
(c)
(d)

4
Without {a, c} 6, with {a, c} 2 4, total 14
8
85

5.26
1
3

2
7
5

#%

Trees and Cut-sets

5.27

2
5
4

5.28

9
4
10
2
2
6

5.29
2

10

2
7
4

13

5.30
1
2

#&

Solutions Manual of Elements of Discrete Mathematics

5.31
7

4
5

5.32 A maximum flow, with fv = 7, is

b

3.3
a
7.4

5.3
4.0

d
8.4
1.1 1.0

2.0
c

4.3

z
3.3
Minimum
Cut

5.33 A maximum flow, with fv = 11, is

8.6

b
4.4

2.2
3.2

7.7
1.1
2.0

2.2

5.5

6.1
4.4
3.3

Minimum Cut

5.34 A maximum flow, with fv = 20, is

5.5
12.2

10.7

1.1

8.3

6.6

6.6

4.4

5.5
6.2

3.3

1.1

12.6
a

6.6

3.3

8.8

1.1

2.2

10.0

5.5

4.4

10.2
3.3

2.0
6.5

3.3
6.2

1.1
6.0
Minimum
Cut

6.0
1.1

6.2

4.0
3.3

6.0

2.0
5.3

10.7

3.3
10.7

6.4

#'

Trees and Cut-sets

5.35 Finding a maximum flow in the following transport network reveals that
the demands of all three depots can be met by having factory x1 make 30
units, x2 10 units and x3 10 units.
X1
40.30
a

20.15
20.10 X2
10.10

Minimum
Cut

10.5
10.10

10.10

Y1

5.5

15.15

10.10

15.15
10.10

5.5
10.0 20.20

20.20

30.20

YL 25.25

10.10

Minimum
Cut

Y3

X3

10.10

5.36 fV = 10
4.4
2.2

3.2

4.4

5.4

2.0

2.2
3.0

2.2

2.2
3.0

2.2

3.2

3.0

2.2

2.2
3.0

2.2

5.5
3.1

3.3

4.2

Mimimum
Cut

5.37 (a) A flow in the following transport network specifies a loading plan for
some or all of the equipment such that no two similar units are on the
same plane. Since the capacity of the cut shown below is 27, there can
be no flow having value 28. Thus, not all the equipment can be so
loaded.
E1

E2

P1

E3

P2

E4

P3

4
a

4
4
4
4

P4

E6
P5

Equip
Types

E5

E7

8
8

All adges have

capacity 1.

Cargo
Planes

4
Cut with
Capacity of 27

$

Solutions Manual of Elements of Discrete Mathematics

(b) Applying the labeling procedure to the transport network of part (a),
with capacities of edges incident with the sink modified, yields the
following loading plan as one possible solution.

5.38

5.38

P1

P2

P3

P4

P5

E1
E2

x
x

x
x

x
x

x
x

E3
E4

x
x

x
x

x
x

E5

E6

E7

x
x1

x1

2.2
5.5
2.1 2.2
x2 2.2
2.0
3.5
2.1
a
2.1
1.1
x3
2.0
2.2 2.0
2.1
2.1
Minimum
2.0
Cut
x4

4.4
x2

3.3
z

x3 2.2
2.2
x4

Minimum
Cut

f(xi, x j) indicates the number of directed edges in G from xi to xj

x1

x3

x2

x4

5.39 (a) Define the capacity of a cut as

R| a (i j )
a(P, P) = S
|T 0

if there are no edges from P to P

i P , j P

otherwise

A Minimum flow-maximum cut theorem:

In a transport network in which the flow in each edge is lower
bounded only, the minimum value that a flow can achieve is equal to
the maximum value of the capacities of the cuts in the network.

$

Trees and Cut-sets

(b) Modified labeling procedure.

Assume an initial feasible flow.
Label the sink z with (, )
Label a vertex y adjacent to z with (z , d(y))
d(y) = f(y, z) a(y, z), if f(y, z) > a(y, z).

where

Do not label otherwise.

Label a vertex x adjacent to a labeled vertex y and (y , d(x))
where

d (x) = min [(f(x, y), a(x, y)), d (y)], if f(x, y) > a(x, y).

Do not label otherwise.

Label a vertex w adjacent from a labeled vertex y with (y +, d(w)) where
d(w) = d(y).
(It is always possible to label a vertex adjacent from a labeled vertex.)
Each time the source a is labeled, reduce the flow in accordance
with the labels and begin again.
The algorithm terminates when the source cannot be labeled. At that
point, if the unlabeled vertices are denoted P, and the labeled vertices

P , then the cut (P, P ) is a maximum cut with no edges from P to P

and each edge from P to P carrying a minimum flow.
5.40

Maximum
cut

ME

20.20
20.35

EE

20.20

10.10

5.10
MT10.10

30.30

5.40

5.10

40.40

II

5.10
0
10.1
15.15
10.10

5.1

20.25

III

6.5
5.5

CT
Category

Project

0.1

5.41

0.0

0.1
1.1
1.1
1.1
1.1

5.41

40.40

0.0

0.1

0.0

1.1
1.1
1.1

0.1
0.1

1.2
1.2

0.1

1.2
1.1

0.0

0.1

Solutions Manual of Elements of Discrete Mathematics

KGGP

5.42
X1
40.45
23.25

5.42

50.55

5.5
20.20
10.10

10.10
5.5
10.10
X2
5.5
2.5
5.5
X3

5.5
10.10

15.15
C1

30.35
25.25

C2

20.35
C3

50.50
Maximum
Cut

All capacities and flows are in thousands of dollars.