Feb 09, 2023  
2021-2022 Undergraduate Academic Catalog 
2021-2022 Undergraduate Academic Catalog [ARCHIVED CATALOG]

Add to Portfolio (opens a new window)

MA 2320 - Introduction to Graph Theory

3 lecture hours 0 lab hours 3 credits
Course Description
This course introduces a sampling of fundamental concepts and results in graph theory. Topics include graph isomorphisms, trees and connectivity, matching and covering, planarity and colouring, and Ramsey’s Theorem. Graph algorithms for solving the assignment problem and the max-flow problem will also be discussed. (prereq: MA 1830  or MA 2310 )
Course Learning Outcomes
Upon successful completion of this course, the student will be able to:
  • Demonstrate knowledge of basic terminology associated with graphs, such as isomorphisms, trees, connectivity, planarity, colouring, and matchings
  • Demonstrate knowledge of fundamental results in graph theory, such as Konig’s Theorem, Hall’s Theorem, Kuratowski’s Theorem and the 4-Colour Theorem
  • Be able to apply various techniques (e.g. mathematical induction, proof by contradiction) to construct basic proofs for statements involving graphs
  • Model simple real world problems using graph theory
  • Be able to solve instances of the assignment problem and the max-flow problem using appropriate graph algorithms

Prerequisites by Topic
  • Basic concepts of college algebra
  • Basic concepts of set theory
  • Basic concepts of logic and proofs 

Course Topics
  • Basic definitions and notions for graphs
  • Matching and covering
  • Planarity and colouring
  • Graph algorithms
  • Ramsey Theory

Edward Griggs

Add to Portfolio (opens a new window)