Undergraduate Course: Combinatorics and Graph Theory (MATH10072)
Course Outline
School  School of Mathematics 
College  College of Science and Engineering 
Course type  Standard 
Availability  Available to all students 
Credit level (Normal year taken)  SCQF Level 10 (Year 3 Undergraduate) 
Credits  10 
Home subject area  Mathematics 
Other subject area  None 
Course website 
None 
Taught in Gaelic?  No 
Course description  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. 
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) 
Additional Costs  None 
Information for Visiting Students
Prerequisites  None 
Displayed in Visiting Students Prospectus?  No 
Course Delivery Information

Delivery period: 2013/14 Semester 1, Available to all students (SV1)

Learn enabled: Yes 
Quota: None 
Web Timetable 
Web Timetable 
Course Start Date 
17/09/2013 
Breakdown of 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 )

Additional Notes 

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

Exam Information 
Exam Diet 
Paper Name 
Hours:Minutes 


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. 
Assessment Information
See 'Breakdown of Assessment Methods' and 'Additional Notes' above. 
Special Arrangements
None 
Additional Information
Academic description 
Not entered 
Syllabus 
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. 
Transferable skills 
Not entered 
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 
Study Abroad 
Not Applicable. 
Study Pattern 
See 'Breakdown of Learning and Teaching activities' above. 
Keywords  CGT 
Contacts
Course organiser  Dr Aram Karakhanyan
Tel: (0131 6)50 5056
Email: aram.karakhanyan@ed.ac.uk 
Course secretary  Mrs Kathryn Mcphail
Tel: (0131 6)50 4885
Email: k.mcphail@ed.ac.uk 

