HMC Math 55: Discrete Mathematics (Spring, 1999)
Homework

### Assignment #13 (due Wed. 5/5):

Section 43 (pg 315): 4, 5, 6
Section 44 (pg 324): 3 (... see 13A), 4
13A: Extend the proof from Exercise 44.3... 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 325) is nonplanar.
(Note1: You do not need to write out a solution to Exercise 44.3 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.)

### Assignment #12 (due Fri. 4/30):

Section 40 (pg 296): 5
Section 41 (pg 302): 4, 6
Section 42 (pg 308): 2 (Bonus: 3 or 4)
12A: Use an extremal argument to prove that any graph (with at least one edge) has at least two vertices whose deletion does not disconnect the graph. (Recall that deleting a vertex from a graph also requires that all its edges be deleted.)
12B: 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.
12C: 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 graph with n vertices has n-1 edges and no cycles, then it is connected (and hence a tree).

### One Calorie Assignment #11 (due Fri. 4/23):

Section 38 (pg 283): 4, 5, 6, 11, 15
11A: Using techniques and results from class, prove 18 -> (4,4). (In English, "In any group of 18 people there must be 4 mutual friends or 4 mutual strangers.")
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 and find it! Look up "Ramsey Theory", find a graph with this property, and attach a photocopy to your homework.

### Assignment #10 (due Fri. 4/16):

Section 30 (pg 225): 11defg, 12, 13, 14
Section 37 (pg 273): 1, 2, 3

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

Section 31 (pg 235): 10 (this was more or less done in class)
Section 32 (pg 242): 1, 2, 3, 6
Section 33 (pg 249): 1, 2, 6
(In 33.6, "Find the equivalence classes mod H" means "find the right cosets of H.")

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

Section 28 (pg 211): 4ab, 13abde
Section 31 (pg 235): 2, 5, 7, 8, 12
Bonus: 28.10

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

Section 27 (pg 201): 16
Section 28 (pg 211): 2ab, 3ab
Section 30 (pg 224): 2, 5, 9
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")
7B: Prove that log10 2 is irrational.
(Optional) (also due Wed. 3/24): Here's an optional extra credit problem for you to ponder while you're suffering discrete withdrawl over spring break. Please work it yourself, and do not consult others (in our class or otherwise) for assistance.

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

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

Section 26 (pg 190): 1ab, 2ab, 4
Section 27 (pg 201): 4, 9, 10, 15, 17
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

### Assignments #1-5

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