Color every point of the plane so that any two points at distance exactly 1 receive different colors. What is the smallest number of colors for which this is possible? It is known that the answer is 5, 6 or 7. Determine it.
Prove that the regions of any map drawn in the plane can be colored with at most four colors so that any two regions sharing a border of positive length get different colors. Equivalently, prove that every planar graph is 4-colorable.
Königsberg had four land masses, two river banks and two islands. One island was joined to each bank by two bridges, the other island to each bank by one bridge, and a seventh bridge joined the two islands. Is there a walk that crosses every bridge exactly once? More generally, which connected…
A closed knight's tour on an board is a sequence of knight moves that visits every square exactly once and ends a knight's move away from the starting square. For which does a closed tour exist? As a first step, prove that none exists when and are both odd.
A convex polyhedron has vertices, edges and faces. Prove that .