Below you can find my hand-written lecture notes for the course Discrete Structures I at the University of Heidelberg. It is based mostly in following references:

• Graph Theory, by Reinhard Diestel
• Introduction to Graph Theory, by Douglas West
• Combinatorial Optimization, by Bernhard Korte and Jens Vygen

Here you can find the typed lecture notes taken by my student, Lucian von Hagen, based on the classes.

Lecture 1:

• Basic notation and definitions
• Graph isomorphisms
• The hand-shaking lemma
• For every $G$ there is $H$ such that $H$ is $\Delta(G)$-regular and $G \subseteq H$.

Lecture 2:

• Existence of subgraphs with large minimum degree
• Lower bounds for the size of the longest path and longest cycle in terms of the minimum degree
• Walks, distance and their basic properties
• Diameter, girth and their relationship

Lecture 3:

• Moore’s theorem: lower bound on the number of vertices of a graph with large minimum degree and large girth
• Corollary: Logarithmic upper bound on the girth for graphs with minimum degree at least 3
• Acyclic graphs, trees and leaves

Lecture 4:

• Equivalent definitions of tree
• Algorithms, running time and function growth
• Decision problems
• The classes P and NP

Lecture 5:

• Examples of classical problems in P and in NP
• The classes co-NP, NP-hard and NP-complete
• The graph scanning algorithm and its running time

Lecture 6:

• BFS, DFS and their main properties

Lecture 7:

• The Kruskal’s algorithm for finding minimum spanning trees
• Euler tours
• A connected graph is Eulerian if and only if all vertices have even degree

Lecture 8:

• Dirac’s theorem
• Chvátal’s theorem

Lecture 9:

• The travelling salesperson problem (TSP) and the metric TSP
• The double tree algorithm is a 2-approximation algorithm for the metric TSP
• The Christofides’ algorithm is a 3/2-approximation algorithm for the metric TSP

Lecture 10:

• A graph is bipartite if and only if it does not contain cycles of odd length
• Matchings, vertex covers and König’s theorem

Lecture 11:

• Hall’s theorem
• Every $k$-regular bipartite graph has a perfect matching (1-factor)
• Every $2k$-regular graph has a 2-factor
• Statement of Tutte’s theorem and the Gallai decomposition theorem

Lecture 12:

• Proof of Tutte’s theorem and the Gallai decomposition theorem
• If a graph is 3-regular and 2-edge-connected, then it has a perfect matching
• The Hopcroft-Karp algorithm

Lecture 13:

• The Hopcroft-Karp algorithm for finding matchings in bipartite graphs

Lecture 14:

• Upper bounds on the running time of the Hopcroft-Karp algorithm
• Connectivity and separations
• Mader’s theorem on the existence of $k$-connected subgraphs with large average degree

Lecture 15:

• Menger’s theorem and a generalisation
• Caracterisation of $k$-connectivity via internally disjoint paths between every pair of vertices