Undergraduate Course: Combinatorics and Graph Theory (MATH10072)
|School||School of Mathematics
||College||College of Science and Engineering
||Availability||Available to all students
|Credit level (Normal year taken)||SCQF Level 10 (Year 3 Undergraduate)
|Home subject area||Mathematics
||Other subject area||None
||Taught in Gaelic?||No
|Course description||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.
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)
|Additional Costs|| None
Information for Visiting Students
|Displayed in Visiting Students Prospectus?||No
Course Delivery Information
|Delivery period: 2013/14 Semester 1, Available to all students (SV1)
||Learn enabled: Yes
|Course Start Date
|Breakdown of 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
|Breakdown of Assessment Methods (Further Info)
|Main Exam Diet S2 (April/May)||MATH10072 Combinatorics and Graph Theory||2:00|
|Main Exam Diet S1 (December)|| Combinatorics and Graph Theory (Visiting Students Semester 1 only)||2:00|
Summary of Intended Learning Outcomes
|1. Ability to solve counting problems
2. Understanding the elements of Graph Theory.
|See 'Breakdown of Assessment Methods' and 'Additional Notes' above.|
||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.
||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
||See 'Breakdown of Learning and Teaching activities' above.
|Course organiser||Dr Aram Karakhanyan
Tel: (0131 6)50 5056
|Course secretary||Mrs Kathryn Mcphail
Tel: (0131 6)50 4885
© Copyright 2013 The University of Edinburgh - 10 October 2013 4:52 am