Homework 7

Written assignment (assigned November 14, due November 21)

This homework covers the material in chapter 23 of the textbook.

Please note: your solutions should be readable, and justifications should be given for steps in the proofs. Elegance counts!

1. Do exercise 23.1-3 on page 468. (10 points)

2. Do exercise 23.2-4 on page 476. (10 points)

3. Do exercise 23.2-6 on page 476. (10 points)

4. Do exercise 23.3-1 on pages 483-484. (10 points)

5. Do problem 23-3, part (a), on page 496. (10 points)
   Definitions: The degree of a vertex is the number of its neighbors (i.e., how many vertices are adjacent to it); in a directed graph, the in-degree of a vertex is the number of its in-neighbors, and out-degree of a vertex is the number of its out-neighbors.
   The definition of a cycle is given on page 88 of CLR: viz., in a directed graph, a path v₀, v₁, ..., v_k forms a cycle if v₀ = v_k (i.e., if it is closed) and the path contains at least one edge.

   Challenge Problems (optional)

   • Show that if G is a bipartite graph with V vertices and E edges, then E is less than or equal to V²/4.

   • Definition: The complete bipartite graph K_m,n is an undirected graph with vertex set V partitioned into a subset V₁ of m elements and a subset V₂ of n elements such that two vertices are connected by an edge if and only if one is in V₁ and the other is in V₂.
     Understand what this definition means and draw K_{2, 3} and K_3,3.

   Gerry Brady
   Wed Nov 14 23:52:10 CST 2001