Syllabus of Math 381, Graph Theory
Textbook
Introductory Combinatorics, 3rd edition, by Richard A. Brualdi.
List of material to be covered
This list is not absolutely fixed. The material mentioned in Chapters
11 and 13 forms the heart of the course but it is
supplemented and may be partially replaced by other material.
Chapter 1: What is Combinatorics?
Some famous problems of graph theory. Section 4: The 4-color problem. Section 6: Shortest routes.
Chapter 11: Introduction to Graph Theory
Section 1: Basic properties; isomorphism; adjacency matrix; connectedness. Section 2: Eulerian trails. Section 3: Hamilton chains and cycles. Section 4: Bipartite graphs. Sections 5, 7: Trees. Possibly Section 6: The Shannon switching game.
Chapter 12: Digraphs and Networks
Section 1: Digraphs. Possibly Section 2: Networks.
Chapter 13: More on Graph Theory
Section 1: Chromatic number. Section 2: Planarity. Section 3: Planar coloring. Section 4: Independence and clique numbers. Section 5: Connectivity.
Chapter 9: Matchings in Bipartite Graphs
Possiby Sections 1-2: Matchings.
Other optional topics
(not necessarily listed here) may be covered at the discretion of the instructor. Possible topics include signed graphs, embedding in surfaces.
Go to course home page | announcements | homework
assignments.