HMC Math 55: Discrete Mathematics (Fall, 1999)

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

Section 46 (pg 346): 2, 9
Section 48 (pg 359): 1, 7, 10, 11
Section 49 (pg 368): 2, 4 (see below), 7, 11
12A: 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.
12B: 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 369) is nonplanar.
(Note1: You do not need to write out a solution to Exercise 49.4 seperately... 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.)
BONUS: Recall in class we saw the result that there are n^(n-2) trees on n labelled vertices. The proof (which we didn't see all of) involved drawing a 1-1 correspondence between all such trees and all length n-2 lists (with repetion allowed) of elements from {1, 2, ..., n}. We started the proof be describing how to go from a tree to its corresponding list...
  while E(T) > 2
    delete the leaf with smallest label from T and 
    add the label of this leaf's neighbor to our list
Your job: come up with the inverse algorithm. That is, describe how to take any such length n-2 list and generate the corresponding tree. The tree created from a list L has to be the one that, when subjected to the above algorithm, will generate the list L.
Note: These algorithms are actually functions, and in fact are inverse functions of eachother. Since only 1-1 onto functions can have inverses, and since a 1-1 onto function from A to B implies |A| = |B|, your algorithm actually (more or less) completes the proof.
Some solutions for HW#12

Assignment #11 (due Fri. 12/03):

Section 44 (pg 332): 3, 4, 5, 7
Section 45 (pg 339): 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.

Extra Credit (Optional) (also due Fri. 12/03): 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.
Happy Thanksgiving!
Some solutions for HW#11

Assignment #10 (due Wed. 11/24):

Section 43 (pg 324): 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.
Some solutions for HW#10

2nd Midterm: Monday, Nov. 15

(No homework due Wed. 11/17)

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

Section 35 (pg 264): 13, 14 (then read 15 & 16)
Section 37 (pg 283): 6, 9, 11
(For #11, just give a conjecture... don't prove; but see HW#8A)
Section 38 (pg 290): 1, 4, 8

BONUS: Translate this into english.
Some solutions for HW#9

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

Section 33 (pg 251): 4, 14
Section 36 (pg 276): 2, 4, 9, 13, 14

Some solutions for HW#8

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

Section 32 (pg 241): 15, 18
Section 33 (pg 251): 2abc, 3
Section 35 (pg 264): 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")
Some solutions for HW#7

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

Section 31 (pg 231): 1abe, 2abe, 3
Section 32 (pg 241): 4, 9, 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
Some solutions for HW#6

1st Midterm: Monday, Oct. 11

(No homework due Wed. 10/13)

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

Section 15 (pg 100) (Prove these combinatorially): 6, 8
(Optional hint for #4: *'s & |'s)
Section 16 (pg 109): 1, 4, 5
Section 19 (pg 135): 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) *****

Some solutions for HW#5

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

Section 14 (pg 91): 6, 12, 15, 18, 19
Read Section 17 (pgs 111-116)
Section 17 (pg 116): 2, 3, 10
Section 18 (pg 127): 4, 5 (Prove 4 & 5 by induction, not the techniques of Section 18)
Section 19 (pg 135): 3bd, 8a
Extra Credit: 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

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

Section 6 (pg 34): 7, 10, 12
Section 7 (pg 39): 1, 8, 11
Section 14 (pg 91): 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.

Note: As of this assignment, you must begin each problem by copying the problem statement.
Some solutions for HW#3

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

Section 5 (pg 26): 17, 18, 19ac
Section 6 (pg 34): 3, 6
Section 8 (pg 44): 9
Section 9 (pg 50): 1hik, 2hik, 6
Section 10 (pg 60): 3, 5, 20

Note: This assignment is not compatible with last semester's version of the text
Some solutions for HW#2

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

Section 1 (pg 4): 2, 3bdf
Section 2 (pg 12): 3, 8
Section 3 (pg 19): 6
Section 4 (pg 21): 3
Section 5 (pg 26): 9, 11ab, 14
Also: Read pages 1-26 (Sections 1-5)
Note: This assignment is compatible with last semester's version of the text

Return to: Math 55 Main Page * Greg Levin's Page * Department of Mathematics