MA6043: Graph Theory I, Fall 2025

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.

Slides

• [Fundamentals] last updated 2025/9/2 21:56

• [Tree] last updated 2025/9/10 10:21

Schedule

• Week 1 practice 1

  • 09/01 [Fundamentals] Syllabus, prerequisites

  • 09/03 basic notions, adjacent, incident, neighbor, loop, multiple edge, simple graph, vertex degree, Degree Sum Formula, subgraph and induced subgraph, graph isomorphism, Petersen graph, leaf, complete graph, bipartite graph, order and size of graph, walk, trail, path, cycle, connected graph and component, Konig's Theorem on bipartite graph

• Week 2 practice 2

  • 09/08 Eulerian graph, tournament and king, cut vertex

  • 09/10 Euler's Theorem, even graph, digraph, cut edge, degree sequence, graphic sequence [Tree] equivalent definitions of tree, labeled trees, spanning tree, leaf, Cayley's formula

• Week 3

  • 09/15

  • 09/17

  • Prufer codes, Matrix Tree Theorem

• Week 4

  • 09/22

  • 09/24

  • Prim's and Kruskal's Algorithms and their correctness, [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 5

  • 09/29 No class

  • 10/01

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

• Week 6

  • 10/06 No class

  • 10/08 Test 1

• Week 7

  • 10/13

  • 10/15

  • 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 8

  • 10/20

  • 10/22

  • [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 9

  • 10/27

  • 10/29

  • 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 10

  • 11/03

  • 11/05 No class

  • 
    

• Week 11

  • 11/10

  • 11/12 Test 2

• Week 12

  • 11/17

  • 11/19

  • Last day to drop: 11/21

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

• Week 13

  • 11/24

  • 11/26

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

• Week 14

  • 12/01

  • 12/03

  • 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 15

  • 12/08

  • 12/10

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

• Week 16

  • 12/15

  • 12/17 Test 3

• 01/09 Instructor's deadline to upload scores