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.