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.