Level: III
Semester: 2
Number of Credits: 3
Prerequisites: MATH 2272

 

Course Description

Students taking this course will be expected to have a solid foundation in abstract algebra. For this reason, MATH 2272 is listed as a course prerequisite.

Basic definitions used in Graph Theory are introduced. Terms like valency, graphical sequences, walk, trail, path, connected graph etc. are defined. The concepts of graph isomorphism and connectedness are introduced. Trees are given attention because of their importance in Graph Theory. Algorithms for tree coding are described. Spanning trees, the Spanning Tree algorithm and Matrix Tree Theorem are developed. Classical result in tranversability like Eulerian graphs and Hamiltonian Graphs are given attention. Then the important concepts like planarity and colourability are examined. A description of the proof of Kuratowski’s Theorem from Tutte’s Theorem is provided.

 

Assessment

Coursework                                                                 50%
Final Examination - one 2-hour written paper          50%
Top of Page