Thursday 12:00-16:00, Irinyi 212 room
Lecture: During the exam period, written exams will be announced to test the students' knowledge. Additionally, bonus points can be earned during the semester.
Practice: There will be 2 midterms, on 19th October and 7th December. In the first week of the exam period, one of the midterms can be rewritten on request by the student. Additionally, bonus points can be earned during the semester.
Grades for both courses:
0% – 50%: fail (1)
51% – 62%: pass (2)
63% – 75%: satisfactory (3)
76% – 87%: good (4)
88% – 100%: excellent (5).
1. Basics. Multigraphs and (simple) graphs. Loops and parallel edges. Degrees. Handshake lemma. Complete graph. Connectivity, connected components, trees.
2. Graph realization problem. Degree sequences. Realization by multigraphs. Realization by loopless multigraphs (without a proof).
Realization by simple graphs: Havel—Hakimi-lemma (and algorithm).
3. Enumeration of spanning trees. Spanning trees. Cayley's theorem on the number of spanning trees of Kn. Labeled trees, Prüfer codes.
4. Graph algorithms. Breadth-first transversal, depth-first transversal. Kruskal's algorithm for finding minimum cost spanning tree. Dijkstra's algorithm for finding shortest path in weighted graphs.
5. Network flows. Network, feasible flows. Value of a flow. Cuts. Value and capacity of a cut. Maximum flow, minimum cut theorem.
Augmenting paths. Finding a feasible flow with greater flow value using an augmenting path. Ford—Fulkerson-algorithm.
6. Connectivity. k-edge-connectivity, k-connectivity and the relationship between these notions. Menger's theorems.
7. Matchings. Matchings, and the parameter ν(G). Matchings in bipartite graphs: Kőnig sets and the marriage theorem, Hungarian method.
Matchings in general graphs: Tutte sets and Tutte's theorem. Additional material (not part of the curriculum): Edmond's blossom algorithm.
8. Vertex coloring. Proper vertex coloring, chromatic number. Cliques and the parameter ω(G).
Lower bound for χ(G) in terms of ω(G).
Upper bound for χ(G) in terms of maximum degree, greedy coloring algorithm.
9. Planar graphs. Planar graphs. Four color theorem. The two basic examples of non-planar graphs. Kuratowski's theorem.
10. Edge coloring. Proper edge coloring, edge chromatic number. Vizing's and Shannon's theorems.
Edge chromatic number of bipartite graphs.
11. Eulerian tour and the Chinese postman problem. Eulerian tour. Euler's theorem. Chinese postman problem.
12. Hamiltonian path, Hamiltonian cycle and TSP. Hamiltonian path and cycle. Dirac's theorem (without a proof).
A method for proving the non-existence of Hamiltonian path / cycle. Traveling salesman problem.
The proofs are needed in the same detail (no proof / partial proof / sketch of the proof / full proof etc.) as it was presented in the lecture.
1. Realization of degree sequences
2. Enumeration of spanning trees
3. Network flows
4. Connectivity
5. Eulerian tour
6. Matchings in bipartite graphs
7. Matchings in general graphs
Sample midterm exam #1,
Sample midterm exam #2 [OUTDATED].
Sample final exam #1,
Sample final exam #2.
Components: #1 (a graph with 4 components),
#2 (a graph with 3 components),
#3 (a graph with 3 components).
Tree: #1, #2.
Spanning tree: #1, #2.
Tree traversals: breadth-first search, depth-first search.
Matchings: #1 (non-perfect), #2 (perfect),
#3 (matching in a bipartite graph), #4 (matching in a bipartite graph that covers A),
#5 (perfect matching in a bipartite graph).
Kőnig set: #1, #2.
Proper (vertex) coloring: #1,
#2.
Four color map problem / Four color theorem #1, #2.
Edge coloring: #1, #2.
Eulerian tours: #1 (closed Eulerian tour),
#2 (closed Eulerian tour),
#3 (non-closed Eulerian tour).
Hamiltonian path: #1, #2.
Hamiltonian cycle: #1, #2, #3.
These pictures were mostly collected from the web (see the URLs for the source).
Béla Csaba, Péter Hajnal, Gábor V. Nagy: Graph theory for MSc students in computer science (2019) [Note, textbook]
Douglas B. West: Introduction to Graph Theory (Prentice Hall)
Reinhard Diestel: Graph Theory (Springer-Verlag, free online version)
Benny Sudakov: Graph Theory (electronic lecture notes)
