For Mon. 2/2: Read Section 1.3.

Do for discussion Thurs. 2/5:

Sect. 1.2, # 9 (graphs 1 and 3 only).

Sect. 1.3, ## 1, 2, 5, 11.

## C2, C5(a).

Do for discussion Fri. 2/6:

Sect. 1.3, ## 12-14, 16.

## C3, C5(b).

Hand in Mon. 2/9:

Sect. 1.2, # 10 and the rest of # 9.

Sect. 1.3, # 7.

## C1, C4, C7.

Go to announcements | course information | homework list | previous homework | next homework.

**Notation**: Since I can't use full mathematical notation on the Web, I'll write G^{-}, here only, for the complement of G. I'll write "G isom H" to mean G and H are isomorphic.

C1. **CORRECTION: Omit this problem.**

C2. In the graph F of Figure 1.1.16:

(a) Find a longest path P. (Call its endpoints x and y.)

(b) Pick an edge e of P which lies in a cycle of F. In F - e, find a path connecting x and y.

(c) Pick an edge f of P which does *not* lie in a cycle of F. In F - f , is there a path connecting x and y?

C3. Let G be a graph which has a cycle. Let C be a cycle in G. Let a, b be arbitrary vertices in G, and let e be any edge in C. Explain why, if G has a path connecting a to b, so does G - e.

C4. Show that the graph G_{0} is not a tree by using the proof of the first half of Theorem 1.3.5. Namely, pick any two paths you like between a and e, and use the method in the proof to contruct a cycle in G_{0}.

C5. In G_{2} from Homework I, find the values of

(a) lambda(1, 5), (b) lambda(2, 6).

Use Menger's Edge Theorem to prove you are correct: i.e., find the pairwise edge-disjoint paths that the theorem tells us exist.

C6. The same as C5, but for lambda(v_{3}, v_{5}) in G_{3} from Homework I.