HMC Math 55: Discrete Mathematics (Fall, 1998)

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

Section 40 (pg 289): 4, 5
Section 42 (pg 302): 1, 2, 4, 5 (Hint: see proof of Prop 42.5)
Section 43 (pg 311): 2, (3), 4, 6
12A: Complete the proof 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).
12B: Extend the proof from Exercise 43.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).
(i) Use this fact to give an alternate proof that Petersen's graph (see bottom of pg 311) is nonplanar.
(Note1: You do not need to write out a solution to Exercise 43.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.)

Extra Credit (Optional) (due Wed. 12/2):

Here's an optional extra credit problem for you to ponder while you're pretending to listen to Uncle Fred over Thanksgiving dinner. 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. And be nice to Uncle Fred. He means well.

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

Section 38 (pg 277): 2
Section 39 (pg 283): 5
Section 41 (pg 295): 2, 3, 5
11A: 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.)
11B: Suppose k is the maximum length of a path in a connected graph G. If P and Q are paths of length k in G, prove that P and Q have a common vertex.
11C: 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.

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

Section 37 (pg 270): 2, 4, 5, 6, 11, 14, 15
Note: For #4, just find one that requires more than 4 colors. Bonus points for finding one that requires 7.
10A: The k-cube is the graph whose vertices are all the length k binary sequences, and two vertices are adjacent iff their sequences differ in exactly on place (coordinate). For example, in the 5-cube, 10110 and 10100 are adjacent, but 11011 and 10010 are not.
(i) How many vertices and edges does the k-cube have?
(ii) Draw the k-cube for k=1,2,3 and 4.

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. 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.

Assignments #5-9
Assignments #1-4

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