**MATH 401**

**Graph Theory**

**Units: 3.00**

An introduction to graph theory, one of the central disciplines of discrete mathematics. Topics include graphs, subgraphs, trees, connectivity, Euler tours, Hamiltonian cycles, matchings, independent sets, cliques, colourings, and planarity.

NOTE Given jointly with MATH 801.

NOTE Given jointly with MATH 801.

**Learning Hours:**120 (36 Lecture, 84 Private Study)

**Requirements:**Prerequisite MATH 210/3.0 or MATH 211/6.0*. Recommended Experience with abstract mathematics and mathematical proof, and a good foundation in linear algebra.

**Offering Faculty:**Faculty of Arts and Science

**Course Learning Outcomes:**

- Experience the development of other topics such as Ramsey theory, spectral methods, or random graphs.
- Use an inquiry-based approach to explore bipartite graphs, trees and connectivity, Euler and Hamiltonian paths, graph matchings and colourings, and planar graphs.
- Work with the fundamental concepts of graph theory (cycles, regular graphs, matrix representations, isomorphisms, etc.).