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, trees) , Euler's VE+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.

Information for Visiting Students
Prerequisites  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. 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2022/23, Available to all students (SV1)

Quota: None 
Course Start 
Semester 1 
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
80 %,
Coursework
20 %,
Practical Exam
0 %

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

Main Exam Diet S1 (December)   2:00  
Learning Outcomes
On completion of this course, the student will be able to:
 Solve counting problems.
 Identify properties of graphs (such as Eulerian/Hamiltonian/Planar/Bipartite/Connectedness).
 Solve matching problems using Hall's marriage theorem and equivalent bipartite graph formulations.
 Solve counting problems associated to graphs (such as numbers of paths)

Reading List
Reference books which contain some material relevant to the course:
* A First Course in Combinatorial Mathematics by Ian Anderson
* Aspects of Combinatorics by Victor Bryant.
* Graphs An Introductory Approach, by R J Wilson and J J Watkins
* 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 David Jordan
Tel: (0131 6)50 7210
Email: D.Jordan@ed.ac.uk 
Course secretary  Miss Greta Mazelyte
Tel:
Email: greta.mazelyte@ed.ac.uk 

