MATH 341 (Fall 2009)

MATH 341: Graph Theory

Announcements:
• 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.

Tentative plan:

My plan is to study the following questions in this course:

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 Kn to denote the complete graph on n vertices.

Try to prove the following: No matter how you color the edges of K6 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 K3 or the complement of K3 as an induced subgraph.) It is easier to see that K5 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.

Textbooks:

"Graphs, colourings and the four-colour theorem" by Robert A. Wilson, Oxford University Press, 2002.
"Graph theory" by Reinhard Diestel, Third Edition, Springer, 2005. Visit this link for an electronic edition.

Other Sources:

"A textbook of graph theory" by R. Balakrishnan, K. Ranganathan, Springer, 2000.
"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.

For Further Study:

"Topics in Graph Automorphisms and Reconstructions" by J. Lauri and R. Scapellato, LMS, 2003.
"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.

In the class:

Week 1: Overview, Eulerian circuits
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, republic day holiday
Week 6: Maps on a torus
Week 7: Connectivity, proof of the Kuratowski's theorem
Week 8: Wagner's theorem, the midterm exam
Week 9: Marriage problem, bayram holiday
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, new year's day
Week 15: Cayley graphs, Frucht's Theorem

Lectures are over now. (8 January 2010)