Tuesday 13:00-16:00, Grünwald Géza room
Practice: There will be 2 tests: on 22nd October and on 10th December. In the first week of the exam period, one of the midterms can be retaken on request by the student. Additionally, bonus points can be earned during the semester.
Lecture: During the exam period, written exams will be announced to test the students' knowledge. 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 (presentation). Multigraphs and (simple) graphs. Loops and parallel edges. Degrees. Handshake lemma. Complete graph.
Complement of a graph. Isomorphic graphs.
2. Graph realization problem (presentation). Degree sequences. Realization by multigraphs. Realization by loopless multigraphs (without a proof).
Realization by simple graphs: Havel—Hakimi-lemma (and algorithm).
3. Connectivity and trees (presentation). Vertex removal, edge removal. Sub(multi)graphs, spanning and induced subgraphs.
Walks, trails, paths, cycles. Connected and disconnected graphs. Connected components. Trees. Leaves, number of edges in a tree. Rooted trees. Spanning trees.
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. Capacity of a cut, determining flow value using 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. Applications of network flows. Project selection problem.
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 (presentation). 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. Edge coloring. Proper edge coloring, edge chromatic number. Vizing's and Shannon's theorems. Edge chromatic number of bipartite graphs.
10. 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.
Sample 1st test
Sample 2nd test
Sample exam #1
Sample exam #2
1. Basics. Realization of degree sequences.
2. Connectivity. Trees
3. Basic graph algorithms
4. Network flows
5. Applications of network flows
6. Matchings in bipartite graphs
7. Graph colorings
8. Trails and paths
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)
