MA6043: Graph Theory I, Fall 2024

References

1. Douglas B. West. Introduction to graph theory. Vol. 2. Upper Saddle River: Prentice hall, 2001.

2. John Adrian Bondy and Uppaluri Siva Ramachandra Murty. Graph theory. Springer Publishing Company, Incorporated, 2008.

3. Douglas B. West. Combinatorial mathematics. Cambridge University Press, 2021.

4. 張鎮華、蔡牧村。演算法觀點的圖論（修訂版）。國立台灣大學出版中心，2020。

5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.

Slide  (last updated on 2024/12/25 10:19)

Schedule

• Week 1, 09/11 HW1

  • [Fundamentals] Syllabus, prerequisites, basic notions, adjacent, incident, neighbor, loop, multiple edge, simple graph, vertex degree, Degree Sum Formula, subgraph and induced subgraph, graph isomorphism, k-regular graph, Petersen graph, leaf, complete graph, bipartite graph, order and size of graph, walk, trail, path, cycle

• Week 2, 09/18 HW2

  • Eulerian graph, Euler's Theorem, Konig's Theorem on bipartite graph, even graph, digraph, tournament and king, connected graph and component, cut vertex, cut edge, degree sequence, graphic sequence, leaf

• Week 3, 09/25 HW3

  • [Tree] Equivalent definitions of tree, labeled trees, Prufer codes, Cayley's formula, Matrix Tree Theorem, spanning tree

• Week 4, 10/02 Class canceled due to typhoon

• Week 5, 10/09 HW4

  • Prim's and Kruskal's Algorithms and their correctness, distance in graph, shortest path problem, Dijkstra's Algorithm

• Week 6, 10/16 HW5

  • [Matching and factor] M-alternating and M-augmenting path, symmetric difference of two matchings, maximum matching, Berge's Theorem, *Hall's Theorem, vertex cover, independent set

• Week 7, 10/23 HW6

  • Edge cover, *Konig-Egervary Theorem, Gallai's Theorem, stable matching, Gale-Shapley Algorithm

• Week 8, 10/30 HW7, things to remember for midterm

  • k-factor, matching in general graph, odd component, Berge-Tutte Formula, Tutte's Theorem, Petersen's Theorems on 3-regular and 2k-regular graph

• Week 9, 11/06 Midterm exam

• Week 10, 11/13 HW8

  • [Connectivity and path] Connectivity, edge connectivity, separating set or vertex cut, edge cut, disconnecting set, k-connected and k-edge-connected graph, Whitney's theorem, 2-connected graph

• Week 11, 11/20 No class

• Week 12, 11/27 HW9

  • Expansion lemma, ear and ear decomposition, x,y-cut or x,y-separator, internally disjoint x,y-paths, edge-disjoint x,y-paths, X,Y-path, *Menger's Theorems, Fan Lemma, local and global connectivity, U-fan

• Week 13, 12/04 HW10

  • Flow in network, *Max-Flow Min-Cut Theorem, Ford-Fulkerson's Algorithm, integrity Theorem

• Week 14, 12/11 HW11

  • [Planar graph] Faces and their degrees, Euler's Formula, platonic solids, subdivision, triangulation, maximal planar graph

• Week 15, 12/18 HW12

  • Kuratowski's Theorem, graph minor, Wagner's Theorem, outerplanar graph [Graph coloring] clique number, equivalent definitions of k-degenerate graph, line graph, Mycielski's construction, k-critical graph, Four Color Theorem

• Week 16, 12/25

  • Brooks' Theorem, edge coloring, [Hamiltonian graph], Dirac's Theorem, forbidden graph, Mantel's Theorem, Turan's Theorem and Turan graph

• Week 18, 01/08 Final exam

• Week 19, 01/17 Instructor's deadline to upload scores