Dr. Sarah's 4710/5710 Problem Set 1

Problem 1a) I’ve added an eighth bridge to the town of Konigsberg (now Kaliningrad, in Russia). Show that it is now possible to draw a continuous path that crosses each bridge exactly once. Problem 1b) (Grad) We know that if we remove the bridge I added, then no such path can be found between the seven remaining bridges, since this is exactly what Euler proved. Search on the web or in a library, find useful references, and briefly summarize why no such path can be found. Be sure to give proper reference.

Problem 2) The ancient Greeks knew that there were only five regular (convex) polyhedra (also called Platonic solids): the tetrahedron, cube, octahedron, icosahedron, and dodecahedron. Compute each Euler characteristic. For your writeup, be sure to show what V, E, F are for each polyhedra in addition to the corresponding Euler characteristic formula.

	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P
1	*	1	0	0	0						1	1	1	0	1
2	1	1	0	0	0						1	*	1	0	2
3	1	1	1	0	0						1	1	1	0	1
4	1	*	1	0	0
5	1	1	1	0	0
6					0
7	1
8	1	2
9
10	0	0	0	0
11	0	0	0
12	1	1	1
13											0	0	0
14	1	1	1									2				0
15	0	0	0	0	0											1
16	0	0	0	0	0					2	3		1			1

Problem 3) Prove that C13 is 1 in the above minesweeper game. (This is harder – try to prove this by contradiction using the following three cases: C13=0, C13=*, C13>1. Be sure to include an intro and conclusion, as usual, and explain why your proof is complete.

Problem 4a) Write down the negation of the statement “All horses are the same color.” Is the negation statement true or false? Explain. Problem 4b) (Grad) Find the flaw in the following proof that all horses are the same color and explain fully.