- Letter grades were announced by e-mail.
- There will be one midterm exam (40 pts) and one final exam (60 pts).
- Midterm results are sent by e-mail.
- The final exam will be on 18 January Monday at 13.30 in M-04 and M-13. Contents of the exam is everything we covered.
- The make-up exam may be on 22 January. Write to me if you are going to take the make-up and this is a bad date for you.

**1. Euler's K�nigsberg Bridge Problem**

This question marks the birth of graph theory (and topology) according to many writers.

Euler wondered whether it was possible to take a walk in K�nigsberg and cross each of the seven bridges on the river exactly once. In a paper that he published in 1736, he proved that it was not possible. (So, graph theory is 273 years old!)

A more generalized version of this question can now be easily translated into modern graph theory language as follows: Given a connected graph, is there a path which goes through all the edges of the graph exactly once? Such graphs are called Eulerian graphs now. A characterization of such graphs is easy to obtain, and it is usually covered in Math 112.

**2. Hamilton's Around the World Game**

Visit this link to see the icosian game.

A small change in the above question gives us a new problem: Given a connected graph, is there a path which goes through all the vertices of the graph exactly once? Such graphs are called Hamiltonian graphs now. There is no known practical characterization of such graphs. In fact, this problem is an NPC problem according to the computational complexity theory. (There are many NPC problems in graph theory; another example is the Traveling Salesman Problem.)

You may like to try to solve the following: Can a knight visit all the 64 squares of a chessboard exactly once and come back to its original position?

**3. Coloring Problems**

Which maps are 2-colorable? 3? 4? 5? It is easy to prove that all maps are 5-colorable, we will do this in the class.

**4. Marriage Problem**

Assume there are n girls and n boys. We have a list of which girls are willing to marry which boys and vice versa. Is there a matching which makes everybody happy? If not, is there a matching which makes all the girls happy?

**5. Ramsey Theory**

We use K_{n} to denote the complete graph on n vertices.

Try to prove the following: No matter how you color the edges of K_{6} with red or blue, there will always be either a red
triangle or a blue triangle. (Or more formally, every graph with 6 vertices contains either K_{3} or the complement of
K_{3} as an induced subgraph.) It is easier to see that K_{5} does not have this property, i.e. 6 is the smallest such
number. For this reason, 6 is called the *Ramsey number* for 3.

It is known that R(1)=1, R(2)=2, R(3)=6, R(4)=18. However, it is an open problem to find Ramsey numbers of 5 or greater integers.

**6. Random Graphs**

Assume you have a (finite or infinite) set of vertices, and you decide whether to draw an edge or not between any given pair of vertices by flipping a coin. What happens then? If your vertex set is countably infinite, then with probability 1, you will get the Rado graph.

"Graph theory" by Reinhard Diestel, Third Edition, Springer, 2005. Visit this link for an electronic edition.

"Modern graph theory" by B�la Bollob�s, Springer, 1998.

"A beginner's guide to graph theory" by W.D. Wallis, Birkh�user, 2000.

Matematik D�nyas�, �izgeler �zel Say�s�, 2003-III.

Collected Papers of Paul Erd�s

"The Petersen Graph" by D.A. Holton and J. Sheehan, Australian Mathematical Society, 1993.

"Groups, Graphs and Trees" by J. Meier, LMS, 2008.

"Algebraic Graph Theory" by N. Biggs, Cambridge, 1993.

"Groups Acting on Graphs" by W. Dicks and M.J. Dunwoody, Cambridge, 1989.

Week 2: Euler's formula, Platonic solids, planar graphs

Week 3: Maps, Kempe chains, Kempe's wrong proof of the 4-color theorem

Week 4: Vertex coloring, edge coloring

Week 5: Hamilton cycles,

Week 6: Maps on a torus

Week 7: Connectivity, proof of the Kuratowski's theorem

Week 8: Wagner's theorem,

Week 9: Marriage problem,

Week 10: Infinite graphs, K�nig's Infinity Lemma, de Bruijn-Erd�s Theorem

Week 11: The Rado graph, random graphs

Week 12: Erd�s-Renyi Theorems, Ramsey Theory

Week 13: Properties of almost all graphs, Infinite Ramsey Theorem

Week 14: Automorphisms of graphs,

Week 15: Cayley graphs, Frucht's Theorem