Course Description
Elementary theory of graphs and digraphs. Topics include connectivity, reconstruction, trees, Euler's problem, hamiltonicity, network flows, planarity, node and edge colorings, tournaments, matchings, and extremal graphs. A number of algorithms and applications are included.
Additional Requirements for Graduate Students:
Extra problems on weekly homework.
Athena Title
Graph Theory
Undergraduate Pre or Corequisite
(CSCI 2610 or CSCI 2610E or MATH 3200) and (MATH 3000 or MATH 3300 or MATH 3300E or MATH 3510 or MATH 3510H)
Semester Course Offered
Offered spring
Grading System
A - F (Traditional)
Course Objectives
Students will become familiar with the basic concepts, facts, and methods of graph theory as listed in the topical outline. It is expected that most, though not necessarily all, of those topics will be covered. Students will also learn fundamental applications of graph theory to geometry, chemistry, physics, and computer science.
Topical Outline
1. Connectivity, Eulerian graphs, Hamiltonian graphs 2. Algorithms for shortest paths, Chinese postman problem, and travelling salesman problem 3. Trees and their properties, counting trees, tree algorithms: minimum weight spanning tree, chemical molecule enumeration, and Kirchhoff's laws for elctrical networks 4. Planar graphs 5. Euler's formula for polyhedra, graphs on surfaces 6. Dual graphs 7. Vertex colorings, Brooks' Theorem, coloring maps, edge colorings, chromatic polynomials 8. Digraphs, graph matchings, and transversal theory; network flows
Syllabus