HMC Math 108: Graph Theory (Spring, 2000)
Homework


Assignment #11 (the last) (due Wed. 5/3):

Section 7.2: 2 (the 2nd one), 3, 4
Section 7.3: 8, 19 (the 1st one), 20 (the 2nd one)
Notes: In Sections 7.2 and 7.3, there are some problem numbering issues. Do #2 on pg 268, #19 on pg 286, and #20 on pg 287.
For #20, graders will be allowed to deduct points if they deem your pictures "non-pretty".
Hint: For #7.2.3, you may want to read Theorem 4.2.20.
11A: Formulate the edge-chromatic number of a graph as an integer program.
You will need to define a new "incidence matrix" to achieve this (use the program for chromatic number as a model).
Find the integer dual of your program, and describe the feasible and optimal solutions to it.
BONUS: 7.3.6
BONUS: 4-face-color this map.
Solutions (.gif)

Assignment #10 (due Wed. 4/19):

Section 6.1: 1, 12, 24
Section 7.1: 2, 3ac, 5, 11
10A: In reference to 7.1.3, describe (G')' when G is not connected.
(Proof not necessary, but I want a good description; G' means "dual of G")
BONUS: 7.1.16
Solutions (.gif)

Assignment #9 (due Wed. 4/12):

Section 5.1: 12
Section 5.2: 1, 2
Section 5.3: 2, 4 (heh, heh), 8, 9
BONUS: 5.2.6
Solutions (.gif)

Assignment #8 (due Wed. 4/5 Fri. 4/7):

Section 5.1: 1, 6, 13, 21
Section 5.2: 4
Section 5.3: 20
8A: Prove that if graph G is a connected bipartite interval graph, then G must be a caterpillar (see pg.70).
8B: Which of the following classes of graphs is hereditary: Complete, Edgeless, Connected, Disconnected, Trees, Forests? For each, prove or give a counterexample.
BONUS: 5.1.29
Hints for 5.1.6: For "7-colorable", this is a pattern you may have seen before in my Discrete class (sort of), though I'm not sure I did it every semester. (Great hint, huh?) For "not 3-colorable", you're looking for a 7 vertex unit-distance graph that contains a 5-cycle as a subgraph.
Solutions (.gif)

Assignment #7 (due Wed. 3/29):

Section 4.2: 1, 5, 10, 18
Section 4.3: 2, 5, 6, 9
BONUS: 4.2.8


The Midterm (24 Hour Takehome)
(due in class on Monday, 3/27)

Assignment #6 (due Wed. 3/8):

Section 3.3: 1, 2, 5, 6
Section 4.1: 4, 21, 23, 28abd
BONUS: 4.1.8, 4.1.9

Assignment #5 (due Wed. 3/1):

Section 2.2: 17
Section 3.1: 10, 15, 31
Section 3.2: 1, (2), 4
5A: 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.?

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?)
BONUS: Read Example 3.2.3 on page 111... 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.
BONUS: 3.2.2 (Previously assigned as regular problem... sorry)
Solutions (.gif)

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

Section 3.1: 3, 7, 28
Section 6.2: 2, 3, 7, 11
BONUS: 6.2.9
Solutions (.pdf)

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

Section 2.3: 1, 2, 6, 12, 14
Section 2.4: 2, 5, 8, 12
BONUS: 2.4.6
(Note: For 2.4.8, you may assume G is Eulerian throughout)
Solutions (.pdf)

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

Section 1.4: 3, 11, 13
Section 2.1: 2b, 12, 20
Section 2.2: 3, 10, 22
BONUSes: 1.4.20, 2.2.7
Solutions (.gif)

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

Section 1.1: 10, 15, 23
Section 1.2: 19, 20, 26
Section 1.3: 12, 15
BONUS: 1.1.27(b) (see 1.1.26 for def. of "edge-transitive")
Solutions (.pdf)

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