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