Discrete Mathematics I

Summer 2020

FU Berlin, Mathematics and Informatics

Course Details

Listed below are the administrative details regarding the course.


If you are interested in taking this course, please make sure you register in the Whiteboard system. (Instructions for registration, and for non-FU students.) It is important to do this as soon as possible, so that we can contact you if needed.


In keeping with the university's coronavirus guidelines and maintaining a responsible level of social distancing, all course activities will take place online through the Cisco Webex Meetings platform. Please be sure to have installed and familiarised yourself with any necessary software in advance. Information for setting up an account for FU students can be found in the ZEDAT portal. Once installed, you can test your configuration here.

Starting from the 21st of April, lectures will take place on Tuesdays and Wendesdays, from 14:15 to 15:45 and the exercise classes on Tuesdays from 16:00 to 17:30 and Wendesdays from 08:30 to 10:00. The links to the Webex meetings will be available in the Whiteboard system.


Tibor Szabó Michael Anastos
Arnimallee 3, Room 211a Arnimallee 3, Room 202
szabo at math dot fu-berlin dot de manastos at mi dot fu-berlin dot de

Exams and Requirements

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

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, 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 on Whiteboard every Wednesday, and should be submitted before 23:59 on Monday of the following week.

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
Week 2 The Inclusion-Exclusion Princible:derangements, 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
Week 3 integer partitions, Fibonacci sequence, its generating function and formula Bó Ch 8, MN Ch 12.1-3
Week 4 generating functions, basic operations, examples, product, Catalan numbers Bó Ch 8, MN Ch 12.1-4
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 MN Ch 3.4-6
Week 7 The pigeonhole principle and applications: Chinese Remainder Theorem, Erdős-Szekeres theorem, Ramsey numbers MN Ch 11, Bó Ch 1
Week 8 Posets: Sperner's theorem, Dilworth's theorem , Graph theory: basic definitions, notation, examples MN Ch7.2 We Ch 1
Week 9 Graph theory: proof of Euler's Theorem, Bipartite graphs (examples, basic theorems, characterization) We Ch 1.2
Week 10 Extremal problems (acyclicity, connectivity, Hamiltonicity, triangle-freeness), Trees: characterization, Kruskal's algorithm We Ch 1.3 & 2.1-3
Week 11 Trees: Prufer Codes, Matchings: Berge's Theorem, Hall's Theorem, Petersen's Theorem on 2-factors, Konig's Theorem We Ch 2.1-2, 3.1
Week 12 Colorings: motivation, defintions, examples, simple lower bounds, tightness, perfect graphs, Mycielski's Construction We Ch 5.1, 8.1
Week 13 Planar Graphs: planar drawings, 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, Six Color Theorem, Five Color Theorem, Four Color Theorem (no proof) We Ch 6.1-3
Return to top