Math 428 - Graph Theory

3 credits. Offered in the Fall and Spring semesters, with occasional summer sessions. Official course information. Prerequisites: Math 250; and Math 251 or Math 291.

Description

Math 428 is a course that serves as an introduction to the subject of graph theory. The course includes colorability, connectedness, tournaments, Eulerian and Hamiltonian paths, orientability, and other topics from the theory of finite linear graphs; proofs related to these topics are also included. There may be an emphasis on applications chosen from social, biological, or computer sciences and physical problems.

There can be some overlap between Math 428 and Math 454, both of which are courses in discrete mathematics; some iterations of 454 include coverage on some topics in graph theory.

Topics covered

Topics covered in Math 428 usually include:

  • Paths and cycles
  • Trees
  • Planarity
  • Graph colorings
  • Matchings
  • Connectivity
  • Matroids

Note that the exact list of topics vary by instructor and semester. Additional topics may include Ramsey’s theorem and combinatorial games.

Comments on prerequisites

Unofficial/suggested additional prerequisites: Math 300.

While 300 is not an official prerequisite for 428, the course tends to involve proofs. Thus it is recommended that one is very familiar with induction (strong induction, weak induction, and the method of smallest counterexamples). Some instructors will review induction due to its importance, though this is not guaranteed, so it is advisable to spend some time learning it on your own or taking 300 first.

Resources

Textbook

Possible textbooks for the class include A First Course in Graph Theory by Gary Chartbrand and Ping Zhang; and Introduction to Graph Theory (fourth edition) by Robin Wilson.

Additional materials

Some past course webpages are available online.