Thursday 12:00-16:00, Irinyi 010, Seminar 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 17th October and 5th 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:
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.
Kirchhoff's matrix tree theorem (without a proof).
4. 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.
5. Application of network flows. Project selection. k-edge-connectivity, k-connectivity and the relationship between these notions. Menger's theorems.
6. Graph algorithms. Breadth-first search, depth-first search. Dijkstra's algorithm for finding shortest path in weighted graphs. Kruskal's algorithm for finding minimum cost spanning tree.
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. Good 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. Planar graphs and the four color theorem.
9. Edge coloring. Proper edge coloring, edge chromatic number. Vizing's and Shannon's theorems. Edge chromatic number of complete graphs.
Edge chromatic number of bipartite graphs.
10. Eulerian trails and the Chinese postman problem. Eulerian trails and tours. Euler's theorem. Chinese postman problem.
11. Hamiltonian path, Hamiltonian cycle and the traveling salesman problem. Hamiltonian path and cycle. Dirac's theorem (without a proof).
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 trail
Sample midterm exam #1,
Sample midterm exam #2.
Sample final exam #1,
Sample final exam #2.
Tree: #1, #2, #3.
Spanning tree: #1, #2.
Components: #1 (a graph with 4 components),
#2 (a graph with 3 components),
#3 (a graph with 3 components).
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 blocking set: #1, #2.
Proper (vertex) coloring: #1, #2.
Four color map problem / Four color theorem #1, #2.
Edge coloring: #1, #2.
Tree traversals: breadth-first search, depth-first search.
Eulerian trails: #1 (Eulerian tour),
#2 (Eulerian tour),
#3 (open Eulerian trail),
#4 (open 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).
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)
