Course Overview: This course introduces some central topics in graph theory.
Learning Outcomes: By the end of the course, students should have an appreciation of the methods and results of graph theory. They should have a good understanding of the basic objects in graph theory, such as trees, Euler circuits and matchings, and they should be able to reason effectively about graphs.
Course Synopsis: Introduction. Paths, walks, cycles and trees. Euler circuits. Hamiltonian cycles. Hall's theorem. Application and analysis of algorithms for minimum cost spanning trees, shortest paths, bipartite matching and the Chinese Postman Problem.
