Undergraduate Course: Combinatorics and Graph Theory (MATH10072)
Course Outline
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 
SCQF Credits  10 
ECTS Credits  5 
Summary  A first course in combinatorics and graph theory: Graphs, Euler's VE+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), Euler's VE+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.
Polya counting.
Counting paths in graphs.

Entry Requirements (not applicable to Visiting Students)
Prerequisites 
Students MUST have passed:
Fundamentals of Pure Mathematics (MATH08064)

Corequisites  
Prohibited Combinations  
Other requirements  Must not have taken :
MATH08010 Discrete Mathematics (Year 2) or MATH09001 Discrete Mathematics (Year 3) 
Information for Visiting Students
Prerequisites  None 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2015/16, Available to all students (SV1)

Quota: None 
Course Start 
Semester 2 
Timetable 
Timetable 
Learning and Teaching activities (Further Info) 
Total Hours:
100
(
Lecture Hours 22,
Seminar/Tutorial Hours 5,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
69 )

Assessment (Further Info) 
Written Exam
95 %,
Coursework
5 %,
Practical Exam
0 %

Additional Information (Assessment) 
Coursework 5%, Examination 95% 
Feedback 
Not entered 
Exam Information 
Exam Diet 
Paper Name 
Hours & Minutes 

Main Exam Diet S2 (April/May)  Combinatorics and Graph Theory (MATH10072)  2:00  
Learning Outcomes
1. Ability to solve counting problems
2. Understanding the elements of Graph Theory.

Reading List
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 
Additional Information
Graduate Attributes and Skills 
Not entered 
Study Abroad 
Not Applicable. 
Keywords  CGT 
Contacts
Course organiser  Dr Aram Karakhanyan
Tel: (0131 6)50 5056
Email: aram.karakhanyan@ed.ac.uk 
Course secretary  Mr Thomas Robinson
Tel: (0131 6)50 4885
Email: Thomas.Robinson@ed.ac.uk 

