HMC Math 55: Discrete Mathematics (Fall, 2000)
Homework

### Assignment #13 (due Fri. 12/08):

Section 46 (pg 383): 2, 9
Section 48 (pg 399): 1, 7, 10, 11
Section 49 (pg 409): 2, 4 (see below), 7, 11
13A: Do the proofs for the following pieces of the "equivalent conditions for trees" theorem...
(i) Prove that a graph G is a tree iff for any two vertices u, v in V(G), there exists a unique path between u and v.
(ii) Prove that if a connected graph with n vertices has n-1 edges, then it has no cycles (and hence a tree). Hint: Start deleting edges in cycles.
13B: Extend the proof from Exercise 49.4... Let G be a planar graph with n vertices and m edges, and g an integer between 3 and n (inclusive).
(i) Prove that if the smallest cycle in G has at least g edges, then m <= g(n-2)/(g-2).
(ii) Use this fact to give an alternate proof that Petersen's graph (see pg 410) is nonplanar.
(Note1: You do not need to write out a solution to Exercise 49.4 separately... simply show it to be a special case of this problem.)
(Note2: The size of the smallest cycle is known as the girth of a graph.)
Weekly thing
Some solutions for HW#13 (Yes, I know it says #12)

### Assignment #12 (due Fri. 12/01):

Section 44 (pg 368): 3, 4, 5, 7
Section 45 (pg 375): 6, 9
Section 47 (pg 352): 2, 3
11A: Use an extremal argument to prove that any connected graph (with at least one edge) has two vertices whose simultaneous deletion does not disconnect the graph. (Recall that deleting a vertex from a graph also requires that all its edges be deleted.)
11B: Draw an Eulerian graph with an even number of vertices (no isolated ones) and an odd number of edges, or prove that this is impossible.

(Optional) (also due Fri. 12/01): Here's an optional extra credit problem for you to ponder while you're suffering from Discrete withdrawl over Thanksgiving dinner. Please work it yourself, and do not consult others (in our class or otherwise) for assistance. Turn it in to me and do not attach it to your homework.

A Martian appears before freelance mathematicians Sam and Max and says "I am thinking of two numbers X and Y where 3 <= X <= Y <= 97. I'll tell Sam their sum, and Max their product, and then, because I'm just a lame plot device to drive this problem, I'll disappear." After he does all of this, the following conversation ensues....

Sam: "You do not know what X and Y are."
Max: "That was true, Sam, but now I do."
Sam: "And now I do too, little buddy."
Max: "Sam, do you ever get the feeling you're nothing but a lame plot device?"

Determine X and Y.
Hint
Weekly thing
Some solutions for HW#12 (Yes, I know it says #11)

### Assignment #11 (due Wed. 11/22):

Section 43 (pg 360): 2, 4, 6 , 8, 13, 16, 17
(For #6, the "7 colors" part is optional)

BONUS: Now that we have "18 -> (4,4)", we show that r(4,4)=18 by showing that "17 -> (4,4)" is false. We do this by finding a graph on 17 vertices with clique and independence numbers both equal to 3. Find such a graph. When I say find, in this case I do not mean construct. This would be rather hard (although you're welcome to try). Instead, go to the library (or anywhere else) and find it! Look up "Ramsey Theory", find a graph with this property, and attach a photocopy to your homework. You can look anywhere you like for this graph except a classmate's homework.
Weekly thing
Some solutions for HW#11

### Low Fat Assignment #10 (due Mon. 11/13):

Section 35 (pg 294): 13, 14 (then read 15 & 16)
Section 38 (pg 323): 8 (this means "Find the cosets of H")

Weekly thing | Something else
Some solutions for HW#10

### Assignment #9 (due Wed. 11/8):

Section 37 (pg 315): 2, 6, 9, 11
(For #11, just give a conjecture... don't prove; but see HW#8A)
Section 38 (pg 323): 1, 4
(Recall that Problem 9A originally appeared on last week's homework)

Weekly thing
Some solutions for HW#9

### Assignment #8 (due Wed. 11/1):

Section 33 (pg 281): 4, 14
Section 36 (pg 308): 2, 4, 9, 13, 14

Weekly thing
Some solutions for HW#8

### Assignment #7 (due Wed. 10/25):

Section 32 (pg 269): 15, 18
Section 33 (pg 281): 2abc, 3
Section 35 (pg 294): 2, 10, 12, 19
7A: Using prime factorizations, prove the following:
(i) If a|bc and gcd(a, b) = 1, then a|c.
(ii) If gcd(a, b) = 1, then gcd(a^2, b^2) = 1. (a^2 means "a squared")
Weekly thing
Some solutions for HW#7

### Assignment #6 (due Fri. 10/20):

Section 31 (pg 259): 1abe, 2abe, 3
Section 32 (pg 269): 4, 9abcef, 10, 13, 17, 19
6A: Rigorously prove parts (ii) and (iv) of Theorem 1.1, namely that
(ii) If a|b and b|c, then a|c
(iv) If a,b>0 and a |b, then a<=b.
6B: Use Euclid's Algorithm to find...
(i) gcd(812, 238)
(ii) Integers x, y where 812x + 238y = gcd(812, 238)
(iii) Integers x, y where 51x + 20y = 15
Weekly thing
Some solutions for HW#6

### 1st Midterm: Takehome, Due Monday, Oct. 9

(No homework due Wed. 10/11)

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

Section 15 (pg 114) (Prove these combinatorially): 6, 8
(Optional hint for #6: *'s & |'s)
Section 16 (pg 124): 1, 4, 5
Section 19 (pg 154): 14
5A: For each of the following "stars & bars" notations, name the corresponding multiset and the set of candidates from which it was chosen (i.e., for "*|**|", the correct answer is "<1,2,2> from {1,2,3}"... since 3 *'s indicate a size k=3 multiset and 2 |'s indicate a size n=2+1 candidate pool).
(i) | | | |*****
(ii) ***| | |**
(iii) | |*****| | |
(iv) *| |**| |**| |
(v) *|**|***|
(vi) *****

Weekly thing
Some solutions for HW#5

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

Section 14 (pg 104): 6, 12, 15, 18, 19
Section 17 (pg 132): 2, 3, 10
Section 18 (pg 145): 4, 5 (Prove 4 & 5 by induction, not the techniques of Section 18)
Section 19 (pg 154): 3bd, 8a
Section 14, #31. Your output may be in simple ASCII, and may use *'s or something similar. An equispaced font is required. This problem will be worth 10 bonus points (half an assignment), and these points are independent of your score on this assignment. Please print out your picture and your source code and submit them to me directly (do not attach to Assignment #4).
Some solutions for HW#4
Weekly thing

### Assignment #3 (due Wed. 9/20):

Section 6 (pg 40): 7, 10, 12
Section 7 (pg 44): 1, 8, 11
Section 14 (pg 104): 3, 14
3A: In Poker, if a hand is garbage (no two values the same, and no straights or flushes), it's value is determined by the highest valued card in the hand. So how many distinct poker hands have the value "Ace high"? That is, the hand is garbage (5 different values, no straights or flushes), and the highest valued card in the hand is an ace? (Note: Ace has highest value of all 13 values). Hint: These hands are a subset of the garbarge hands we did in class, and the counting process is very similar.

Some solutions for HW#3
Weekly thing

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

Section 5 (pg 29): 17, 18, 19ac
Section 6 (pg 40): 3, 6
Section 8 (pg 51): 9
Section 9 (pg 56): 1hik, 2hik, 6
Section 10 (pg 68): 3, 5, 20

Some solutions for HW#2
Weekly thing

### Assignment #1 (due Wed. 9/6):

Section 1 (pg 4): 2, 3bdf
Section 2 (pg 14): 3, 8
Section 3 (pg 22): 6
Section 4 (pg 24): 3
Section 5 (pg 29): 9, 11ab, 14
Also: Read pages 1-29 (Sections 1-5)
Weekly thing

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