Undergraduate Course: Combinatorics and Graph Theory (MATH10072)
|School||School of Mathematics
||College||College of Science and Engineering
|Credit level (Normal year taken)||SCQF Level 10 (Year 3 Undergraduate)
||Availability||Available to all students
|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.
Graphs (including bipartite, Euler, Hamiltonian, Planar), Euler's V-E+F=2 Theorem, classification of Platonic solids, subdivisions, Kuratowski's Theorem.
Counting sets, subsets, multisets, inclusion/exclusion, applications.
Stirling numbers of first and second kinds, Bell numbers.
Generating functions, binomial identities.
Matching, Hall's Marriage Theorem, assignment problems.
Counting paths in graphs.
Entry Requirements (not applicable to Visiting Students)
|| Students MUST have passed:
Fundamentals of Pure Mathematics (MATH08064)
||Other requirements|| Must not have taken :
MATH08010 Discrete Mathematics (Year 2) or MATH09001 Discrete Mathematics (Year 3)
Information for Visiting Students
|High Demand Course?
Course Delivery Information
|Academic year 2015/16, Available to all students (SV1)
|Learning and Teaching activities (Further Info)
Lecture Hours 22,
Seminar/Tutorial Hours 5,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
|Assessment (Further Info)
|Additional Information (Assessment)
||Coursework 5%, Examination 95%
||Hours & Minutes
|Main Exam Diet S2 (April/May)||Combinatorics and Graph Theory (MATH10072) ||2:00|
| 1. Ability to solve counting problems
2. Understanding the elements of Graph Theory.
|Reference books which contain some material relevant to the course:|
* Discrete Mathematics with Applications, by H. F. Mattson, Jr.
* Discrete Mathematics and Its Applications, by K. H. Rosen
* Discrete Algorithmic Mathematics, by S B Maurer and A Ralston
* Discrete Mathematics with Applications, by Susanna S Epp
Each of these books has a chapter on Counting and a chapter on Graph Theory. A book containing some of the basic material on graphs is :
* Graphs An Introductory Approach, by R J Wilson and J J Watkins
Hall's Marriage Theorem is discussed in
* Introduction to Graph Theory, by R J Wilson
|Graduate Attributes and Skills
|Course organiser||Dr Aram Karakhanyan
Tel: (0131 6)50 5056
|Course secretary||Mr Thomas Robinson
Tel: (0131 6)50 4885
© Copyright 2015 The University of Edinburgh - 18 January 2016 4:24 am