Study abroad in Edinburgh

Course finder

Semester 1

Combinatorics and Graph Theory (MATH10072)

Subject

Mathematics

College

SCE

Credits

10

Normal Year Taken

3

Delivery Session Year

2022/2023

Pre-requisites

Equivalence relations, permutations, set theory, group theory, binomial coefficients. Visiting students are advised to check that they have studied the material covered in the syllabus of each prerequisite course before enrolling.

Course Summary

A first course in combinatorics and graph theory: Graphs, Euler's V-E+F=2 Theorem, Kuratowski's Theorem, Counting sets, Generating functions, Matching, Hall's Marriage Theorem, Polya counting, Counting paths in graphs.

Course Description

Graphs (including bipartite, Euler, Hamiltonian, Planar, trees) , Euler's V-E+F=2 Theorem, subdivisions, Kuratowski's Theorem. Counting sets, subsets, multisets, inclusion/exclusion, applications.Stirling numbers of first and second kinds, Bell numbers, partitions. Generating functions, binomial identities.Matching, Hall's Marriage Theorem, assignment problems.Polya counting.Counting paths in graphs, adjacency matrix.

Assessment Information

Written Exam 80%, Coursework 20%, Practical Exam 0%

Additional Assessment Information

Coursework 20%, Examination 80%

view the timetable and further details for this course

Disclaimer

All course information obtained from this visiting student course finder should be regarded as provisional. We cannot guarantee that places will be available for any particular course. For more information, please see the visiting student disclaimer:

Visiting student disclaimer