i recently met a math postgrad here in prague who has shown me an interesting proof he came up with that the petersen graph (see the current tribe photo) has no 3 edge coloring. it goes like this: call the three colors 'a', 'b', and 'c'. imagine that you have four edges in the arrangement --< (i hope that ascii art is clear). then, if the leftmost edge has the color, say, 'a', then one of the rightmost edges will also have the color 'a'. now, since the petersen graph has a 5-cycle (the outmost ring on the picture), 'a', 'b', and 'c' must all appear at least once in that cycle. now, if you look carefully, you will see that each edge in this five cycle is involved in in two of the --< widgets, with the non-overlapping < parts belonging to the star in the middle. now, since there is an edge on the outside with color 'a', at least two edges in the center star must also have the color 'a', and the same for 'b' and 'c'. that makes 6 edges total, but there are only five edges in the middle! hence there is no 3 edge coloring. i love elegant stuff like this.