### General Information

Course Code | XB_0008 |
---|---|

Credits | 6 EC |

Period | P2 |

Course Level | 100 |

Language of Tuition | English |

Faculty | Faculty of Science |

Course Coordinator | dr. S.R. Dahmen |

Examiner | dr. W. Kager |

Teaching Staff |
dr. S.R. Dahmen |

### Practical Information

You need to register for this course yourself

Last-minute registration is available for this course.

Teaching Methods | Seminar, Lecture |
---|

Target audiences

This course is also available as:

### Course Objective

- The student knows basic concepts from graph theory and can solveproblems about and with those in explicit situations.

- The student knows basic theorems and algorithms from graph theory and

can use these to compute and/or prove certain properties in explicit

situations.

- The student knows basic concepts from combinatorics and can solve

problems about and with those in explicit situations.

- The student knows basic theorems and techniques from combinatorics and

can use these to compute and/or prove certain properties in explicit

situations.

### Course Content

This course is about two (related) subjects, namely Graph Theory andCombinatorics.

A graph consists of points (or vertices) and lines (or edges) connecting

pairs of points. Graphs occur as mathematical models for many situations

in both pure and applied mathematics. Combinatorics involves formulas

and techniques for enumeration.

We treat the following topics.

- Elementary graph concepts

- Trees, spanning trees

- Eulerian and Hamiltonian trails/circuits

- Planarity

- Matchings, flows

- Binomial coefficients and generalisations

- Pigeonhole and inclusion-exclusion principles

- Generating functions

- Recurrence relations

- Permutation groups

### Teaching Methods

Lectures, study sessions and tutorials (total 8 hours per week).Students are also required to hand in a homework assignment every week.

We expect you to dedicate in total about 20 hours per week to this

course.

### Method of Assessment

Your final grade is built up as follows:- a written midterm exam (50%);

- a written final exam (50%).

You will also be required to hand in 6 written assignments. Each of

which will be graded as “sufficient” or “insufficient”. A hand-in

assignment that is initially graded as “insufficient”, may be handed in

a second time.

To pass the course in period 2 you must satisfy the following

requirements:

- your final grade must be at least 5.5 (all students); and

- at least 5 out of your 6 hand-in assignments must have been graded as

"sufficient" (all students); and

- you must have been present in at least 75% of the study sessions and

tutorials (full time students only).

If you do not fulfill these requirements, then you can take the resit

exam. The resit exam then counts for 100% (i.e. any grades from the

midterm and/or final exam in period 2 will no longer be valid) and the

only requirement to pass is to score at least 5.5 on this exam.

### Entry Requirements

Basic Concepts in Mathematics### Literature

John M. Harris, Jeffry L. Hirst and Michael J. Mossinghoff,Combinatorics and Graph Theory (second edition), Springer-Verlag, 2008,

ISBN: 978-0-387-797710-6 (available form the library as e-book)

### Target Audience

First year BSc Mathematics### Additional Information

Participation in at least 75% of the study sessions and tutorials ismandatory (for full time students) in order to pass the course in period

2. This rule does not apply to the resit exam.