HMC Math 104: Graph Theory (Spring, 2001)
Homework

### Assignment #10 (due Wed. 5/2):

Section 6.2: 8
Section 6.3: 17, 32, 34, 35
Section 7.3: 1, 2, 3
Note: For #34, look for pretty pictures. Graders will be allowed to deduct points if they deem your pictures "non-pretty".
Hint: For #6.2.8, you may want to read Theorem 4.2.23.

BONUS: 6.3.14
BONUS: 4-face-color this map.

### Assignment #9 (due Fri. 4/20):

Section 6.1: 11, 17, 18ac, 25
Section 6.2: 4, 6, 12
Section 7.1: 1, 7, 26
BONUS: 7.1.13 (Since there doesn't appear to be a "graph below",
you'll have to figure out what it is as well.)

### Assignment #8 (due Fri. 4/13):

Section 5.2: 5, 6, 7, 37
Section 5.3: 1, 5, 8, 11, 12a, 29
BONUS: 5.2.13, 5.3.12b

### Assignment #7 (due Fri. 3/31):

Section 4.3: 2, 13
Section 5.1: 1, 25, 29, 33, 34, 38
BONUS: 5.1.24
NOTE: Although 5.1.25 claims to be a (+) problem, it was only a (!) problem in the first edition, and was assigned last year. If you choose, rather than trying to solve the problem yourself, you can simply do a Google search for "Chromatic number of the plane", and a solution should turn up. The exact value (between 4 and 7) is unknown, and remains a fairly famous open problem.

### Midterm: Takehome, Due Friday, March 23

(No homework due Wed. 3/21)

### Assignment #6 (due Fri. 3/9):

Section 4.1: 2, 5, 28, 34
Section 4.2: 1, 4, 8, 12
BONUS: 4.2.15

### Assignment #5 (due Fri. 3/2):

Section 3.1: 25, 39
Section 3.2: 8
Section 3.3: 3, 4, 10, 15
BONUS:3.3.18
Recall our result from class...
Thm: If G is 3-regular with no cut edges, then G has a perfect matching.
That this result doesn't hold for 5-regular graphs is covered by the k=5 case of 3.3.18.
(Half credit for finding the graph for the k=5 case).
BONUS: Read Example 3.2.5 on page 125... the corn/plant/government example for weighted matchings/covers. Devise another (at least semi-plausible) real-word problem which the weighted matching/cover problem can model.

### Assignment #4 (due Fri. 2/23):

Section 3.1: 1, 3, 8, 40
Section 7.2: 3, 4, 6
Section 8.6: 20
BONUS:7.2.8

### Assignment #3 (due Fri. 2/16):

Section 1.4: 9, 23, 26
Section 2.3: 16, 20
Section 7.2: 2, 7, 9, 17
BONUS:1.4.16
Some solutions for HW#3

### Assignment #2 (due Fri. 2/9):

Section 2.1: 2b, 4, 17, 37, 47
Section 2.2: 2, 7, 15
Section 2.3: 2, 10
2A: Find the optimal solution of the linear program
```max c'x  s.t.  Ax <= b , x >=0  , where

| 2 1 |       | 12 |
A = | 3 5 |   b = | 30 |   c' = [3 2]
| 1 1 |       |  7 |
```
You may want to use the graphical method shown in class.
What is the dual of this L.P.?

2B: Nerd feed can be mixed from donuts, Mountain Dew, pizza, and Twinkies. The following table shows the cost per ton (in dollars) of each of these, together with the percentage of recommended daily allowances for sugar, fat, and protein that a serving of it fulfills.

 donuts Dew pizza Twinkies %Sugar 70 80 25 55 %Fat 70 20 75 65 %Protein 50 25 85 70 COST 200 75 150 100

We wish to combine these components into a nerd feed that satisfies at least 60% of the daily allowance for sugar and fat while not exceeding 60% of the protein allowance.
Formulate a linear program to mix a nerd feed at minimum cost that meets our allowance restrictions.
BONUSES: 2.2.11, 2.2.19
BONUS: Find the solution for the dual L.P. from 5A.
(Hint: With three variables and only two constraints, one variable will be zero in an optimal solution... why?)
Some solutions for HW#2

### Assignment #1 (due Fri. 2/2):

Section 1.1: 5, 10, 31, 41
Section 1.2: 6, 30, 40
Section 1.3: 2, 8, 9, 40
BONUSES: 1.2.43, 1.3.65
Some solutions for HW#1

Return to: Math 104 Main Page * Greg Levin's Page * Department of Mathematics
Email: levin@hmc.edu