Solutions To Assignment 3

7.5 #38

(a)

The degree of vertices for Km,n are either m or n. For Euler circuit both m and n should be even.

(b)

In addition to the Km,n given in (a), we can also allow for two vertices with odd degree for Hamilto paths. So if m is 2 and n is odd, we will also have Euler path.

7.5 #52

d,c,a,b,e

7.7 #16

Add k-1 edges to join the connected components to make it a connected graph

New edges don't create new regions. r = (e+k-1)-v+2=e+k-v+1.

7.8 #4 Chromatic number 3 (Show the coloring)

7.8 #6 Chromatic number 3 (Show the coloring)

7.8 #8 Chromatic number 4 (Show the coloring)

7.8#20

(a) n-1 if n is even otherwise n

(b)max(m,n)

(c)2 if n is even otherwise 3

(d)n

8.1 #20

(a)

From theorem 5, lower bound is 3.

For upper bound consider the most unbalanced tree as described in the class. Number of leaves will be equal to 4m - 3=81, m = 21. Upper bound is 21.

(b)

From corollary 1, m = 3.

8.2 #8

At least log 8 =3, comparisons will be needed.

The decision tree was discussed in class.

8.5 #10

Four trees by deleting each one of the four edges in the cycle

8.6 #2

{a,b},{a,e},{d,e},{c,d}

7.6#4

You were expected to show the detailed calculations

The final answer is:

weight = 16; path = {a,b,e,h,l,m,p,s,z}