Monday 14:00-16:00, Farkas Gyula room
During the exam period, written exams will be announced to test the students' knowledge. Additionally, bonus points can be earned during the semester.
Grades:
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 (presentation). Matchings, and the parameter ν(G). Matchings in bipartite graphs: Kőnig sets and the marriage theorem, Hungarian method +
worked-out example (in Hungarian).
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. Eulerian trail, Hamiltonian path, Hamiltonian cycle. Eulerian trail. Euler's theorem.
Hamiltonian path and cycle. Dirac's theorem (without a proof). A method for proving the non-existence of Hamiltonian path / cycle.
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.
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 trails: #1 (closed Eulerian trail),
#2 (closed Eulerian trail),
#3 (non-closed Eulerian trail),
#4 (non-closed Eulerian trail).
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)
