I just wanted to remind everyone that Exploration 1 is due next Monday.


Should it not be done by then, just hand it in late.

Here are some loose ends that may help put in better perspective issues we have been discussing in class.

1. Some ideas about cutting edges of a polyhedron to unfold it are here:


2. If G is a connected graph the number of odd-valent vertices in G is even. Thus, when one solves the Chinese Postman problem the number of existing edges that must be repeated to transform the graph into a new graph with an Eulerian circuit is AT LEAST the number of odd-valent vertices in the graph divided by 2, that is, v(odd)/2. However, often the number of actual edges that must be repeated is much larger than v(odd)/2. Thus, for the connected graph with degree sequence 1, 2, 2, 2, 2, 2, 2, 2, 1 (a path of length 7) one has to repeat EVERY edge in order to visit each edge at least once, and return to one's start vertex! (However, v(odd)/2 =1.

How does one find the smallest number of edges to repeat (that is, how many existing edges to duplicated to make the graph even valent)? There is an algorithm due to E. Johnson and Jack Edwards that accomplishes this in polynomial time. However, the algorithm is quite complex and, in this course, we will use "trial and error." For small graphs usually one can visually find an optimal solution without much trouble. Also, for families of graphs, with lots of structure, one find a formula for the number of edges to "eulerize" the graph, that is, repeat existing edges to create a new even-valent graph. Intuitively, one wants to find a pair of odd-valent vertices joined by an edge e and repeat this edge e. If one can find such pairs one wants to find short paths to repeat the edges in, that join odd-valent vertices. Students, and hopefully you, will find these kinds of "puzzles" fun.

3. For better or worse there is no one book that covers the material I want to cover from the point of view I have adopted. However, there are many good accounts of this scattered in various places, some written by me and some by others. I am not suggesting you buy these, but they can be consulted if you want to learn more details about what we are learning.

Graph Theory:

Graphs, Models, and Finite Mathematics, J. Malkevitch and W. Meyer,

For All Practical Purposes, COMAP, (many authors, including me). Any of the 8 editions.

Excursions in Mathematics, P. Tannenbaum and R. Arnold (more recent editions Tannenbaum only).

Graphs and Their Uses, Oystein Ore (new edition with Robin Wilson as an additional author).

There is also Richard Trudeau, Dots and Lines.

Folding Problems

Geometric Folding Algorithms, J. O'Rourke and E. Demaine

This book is very comprehensive and has both technical and expository material. This is not an easy read in my opinion but very rewarding to chew on.

There are lots of materials on:



Joseph O'Rourke wrote an especially nice brief account that appears in the NCTM 2009 Year Book which is devoted to Geometry. This book is edited by Tim Craine and Rheta Rhubenstein.

Yearbook 71, Understanding Geometry in a Changing World

O'Rourke's article can be downloaded from here:


(after the page loads click on the pdf or ps icon.)


The nets of the cube are special cases of polyominoes, hexaminoes, to be more specific.

The standard reference here is:

Solomon Golomb, Polyominoes

See the notes at the end of:


Also, read the notes I handed out.

These topics are also well treated on the web.

You can try:



For example, on Mathworld the search for:

chinese postman problem



where the account is not quite right. (One has to start and end at the same vertex.)

Enjoy your week!


Joe Malkevitch