assignments
due Fri Feb 3
Assignment 1
From Wilson: 2.1, 2.4, 2.5, 3.4, 3.7.
Either write up a proof that there are at most five Platonic solids or write up a proof that the chromatic number of the plane is at least 4 and at most 7.
due Fri Feb 10
Assignment 2
From Wilson: 4.3, 4.4.
- Show that any graph with more than one vertex contains two vertices with the same degree.
The following two problems are well-known and could be solved with 30 seconds of googling. Pleae don't use this approach. The idea is for you to attack them and see what you can manage by yourself (or together, working with each other is encouraged).
- (Try to) solve the 2-pire problem. That is, all 'empries' consist of up to two countries and we want to color our map in the plane such that each empire is given one color and two empires may be given the same color only when their countries do not share any border. What is the smallest number of colors that can be used on any map of 2-pires?
- What is the largest value of n for which K_n can be embedded in a torus? Can you prove it?
Finally, a little binomial coefficient practice:
- Prove that
- Give two proofs that
, one via a counting argument and one via algebraic manipulation. Which do you prefer?
due Mon Feb 27
Assignment 3
Write about graceful labelings.
Some tips:
- Take your audience to be people who know some basic graph theory (they're familiar with the first four chapters of Wilson but nothing else, say) but have never heard of graceful labelings.
- Be sure to clearly state your definitions.
- Use all that clear writing stuff they do down in Dalrymple. Mathematicians like clear writing too. Sentences, paragraphs, punctuation,... give it everything.
- If you prefer to write electronic documents than hand-written ones, a good tip is to refer to "Figure X" whenever you want to draw a picture and give a separate sheet of hand-drawn figures.
- Not an absolute condition, but as a minimum I suggest both
- clearly stating and proving at least one "theorem" (All caterpillars are graceful, for example, or all tripods are graceful given that all snakes have a graceful labeling with the 0 in a specified position.) It does not have to be your own, but give appropriate credit.
- including at least one "conjecture". What property do you think might be true? What evidence have you amassed? What might the steps of an eventual proof look like?
- Everything you write should represent your understanding of what is happening, but there is no need at all that all the work must be yours. Collaboration is encouraged; following up on known results and reporting is too. Just give appropriate citations.
- Enjoy it. Math is fun; writing is fun. This is a chance to do both.
due Wed Apr 4
Assignment 4
From Wilson: 10.2, 10.3, 10.4, 11.1, 11.2.
