Discrete Mathematics I

Summer 2018

FU Berlin, Mathematics and Informatics

Course Details


Lectures will take place in Arinmallee 3, Hs 001 and exercise classes will take place in Arnimallee 6, SR 007/008 on Tuesdays and in Arnimallee 3, SR 119 on Wednesdays.

The lectures will be on Tuesdays and Wednesdays from 14:15 to 15:45.

The exercise classes will be on Tuesdays from 16:15 to 17:45 and Wednesdays from 10:30 to 12:00.

Office hours are on Mondays, from 14:00 to 15:00, and Thursdays, from 14:00 to 15:00, in Arnimallee 3, Room 206.


Tibor Szabó Tamás Mészáros Anurag Bishnoi
Arnimallee 3, Room 211a Arnimallee 3, Room 205 Arnimallee 3, Room 206
szabo at math dot fu-berlin dot de tamas dot meszaros at fu-berlin dot de anurag.2357 at gmail dot com

Exams and Requirements

A full description of the formalities of the course and requirements for successfully completing the course can be found here.

The final exam will take place on Wednesday, July 25th 2018, from 13:00 to 16:00, in Hs 1b Hörsaal (Habelschwerdter Allee 45). (results)

A make-up exam will be offered on Wednesday, October 10th 2018, from 10:00 to 13:00, in HFB/C Hörsaal (Garystr. 35-37). (results

Return to top


Over the course of this semester, we shall cover the following topics:

Enumerative Combinatoric: Elementary counting methods, double-counting, pigeonhole principle, recursions, generating functions, inclusion-exclusion, inversion, Polya theory.
Discrete Structures: Graphs, set systems, designs, posets, matroids.
Graph Theory: Trees, matchings, connectivity, planarity, colourings.


For further reading, you are encouraged to consult either of the texts below:
Return to top


Exercise sheets will be posted below every Wednesday, and should be submitted before 16:15 on Tuesday of the following week.

Assignment Due date Comments
Review sheet Not for submission  
Sheet 1 24/04/2018
Sheet 2 2/05/2018
Sheet 3 8/05/2018
Sheet 4 15/05/2018 11.05: correction to Exercise 2
Sheet 5 22/05/2018
Sheet 6 29/05/2018
Sheet 7 05/06/2018
Sheet 8 12/06/2018 11.06: correction to Exercise 4
practice exam 19/06/2018 solutions
Sheet 9 26/06/2018
Sheet 10 3/07/2018
Sheet 11 10/07/2018
Sheet 12 17/07/2018
Sheet 13 01/08/2018 Bonus sheet
Return to top

Course Progress

As we make our way through the semester, we will provide below a brief review of the topics covered each week.

Week Topics References
Week 1 Elementary counting principles: sum and product rules, double-counting, combinatorial proofs, binomial identities Ai Ch 1.1; Bó Ch 3-4; MN Ch 3.1-3
lecture notes
Week 2 Twelvefold ways of counting; set partitions, Stirling numbers of the second kind, polynomial bases; permutations and cycles, Stirling numbers of the first kind Ai Ch 1.2-4, Bó Ch 5, 6.1
lecture notes (updated 5.5)
Week 3 integer partitions, Fibonacci sequence, its generating function and formula Bó Ch 8, MN Ch 12.1-3
lecture notes (11.5: updated)
Week 4 generating functions, basic operations, examples, product, Catalan numbers Bó Ch 8, MN Ch 12.1-4
lecture notes
Week 5 Exponential generating functions and their products and compositions Bó Ch 8, MN Ch 12.1-4
Week 6 Asymptotic notation, exponential and factorial estimates, Binomial estimates, rate of growth of the partition function, The Inclusion-Exclusion Principle MN Ch 3.4-6
Week 7 The Inclusion-Exclusion Principle:derangements, Posets: Sperner's theorem, Dilworth's theorem MN Ch 7.2, Bó Ch 16.1-2
lecture notes
Week 8 Mobius inversion, The pigeonhole principle and applications: Chinese Remainder Theorem, Erdős-Szekeres theorem, Ramsey numbers MN Ch 11, Bó Ch 1
lecture notes 1
lecture notes 2
Week 9 Ramsey numbers, Graph theory: basic definitions, notation, examples, Handshake lemma We Ch 1
lecture notes 1
lecture notes 2
Week 10 Graph theory: proof of Euler's Theorem, Bipartite graphs (examples, basic theorems, characterization), Extremal problems (acyclicity, connectivity, Hamiltonicity, triangle-freeness) We Ch 1.2-3, 7.2
lecture notes
Week 11 Trees: characterization, Kruskal's algorithm, Prufer codes, Matchings: Berge's theorem, Hall's theorem MN 8.4, We Ch 2.1-2, We Ch 3.1
Week 12 Matchings: Petersen's Theorem on 2-factors, Konig's Theorem, Colorings: motivation, defintions, examples, simple lower bounds, tightness, perfect graphs, Mycielski's Construction Colorings
Week 13 proof of Mycielski's construction, planar drawings, planar graphs, plane graphs, Euler's formula, maximum number of edges in a planar graph, Kuratowski's Theorem (no proof), platonic solids, dual of a graph, maximal planar graphs planar graphs
Week 14 Six Color Theorem, Five Color Theorem, Four Color Theorem (no proof), proof of Kuratowski's theorem notes
Return to top