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/15 14:40

• [Matching and factor] last update 2025/9/17 13:25

• [Connectivity and path] last update 2025/10/14 19:39

• [Planar graph] last update 2025/11/17 11:34

• [Graph coloring] last update 2025/11/24 16:09

• [Hamiltonian graph] last update 2025/12/02 12:06

Schedule (12+11+15=38hr)

• 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, Prufer codes

• Week 3 practice 3

  • 09/15 Matrix Tree Theorem

  • 09/17 [Matching and factor] M-alternating and M-augmenting path, symmetric difference of two matchings, maximum matching, Prim's and Kruskal's Algorithms and their correctness

• Week 4 practice 4

  • 09/22 Berge's Theorem, independent set

  • 09/24 *Hall's Theorem, vertex cover, edge cover, *Konig-Egervary Theorem, Gallai's Theorem

• Week 5 practice 5

  • 09/29 No class

  • 10/01 Stable matching, Gale-Shapley Algorithm, k-factor, matching in general graph, odd component

• Week 6

  • 10/06 No class

  • 10/08 Test 1

• Week 7 practice 7

  • 10/13 review of Test 1 and practice problems

  • 10/15 Berge-Tutte Formula, Tutte's Theorem, Petersen's Theorems on 3-regular and 2k-regular graph [Connectivity and path] Connectivity, edge connectivity, separating set or vertex cut, disconnecting set, k-connected and k-edge-connected graph

• Week 8 practice 8

  • 10/20 Edge cut

  • 10/22 Whitney's theorem, x,y-cut or x,y-separator, internally disjoint x,y-paths, edge-disjoint x,y-paths, local and global connectivity, *Menger's Theorems

  • 2-connected graph, ear and ear decomposition, X,Y-path 

• Week 9 practice 9

  • 10/27 Expansion lemma

  • 10/29 x,U-fan, Fan Lemma, flow in network, Ford-Fulkerson's Algorithm and Edmonds-Karp Algorithm

• Week 10

  • 11/03 *Max-Flow Min-Cut Theorem

  • 11/05 No class

• Week 11 practice 11

  • 11/10 Integrity Theorem, maximum bipartite matching from network flow, proof of Menger's theorems using network flow

  • 11/12 Test 2

• Week 12 practice 12

  • 11/17 Proofs of Menger's and Konig-Egervary Theorems using network flow

  • 11/19 [Planar graph] Faces and their degrees, Euler's Formula, platonic solids

  • Last day to drop: 11/21

• Week 13 practice 13

  • 11/24 Euler's formula for disconnected plane graph

  • 11/26 Subdivision, triangulation, maximal planar graph, Kuratowski's Theorem, graph minor, Wagner's Theorem, outerplanar graph [Graph coloring]

• Week 14 practice 14

  • 12/01 clique number, bounds on chromatic number

  • 12/03 equivalent definitions of k-degenerate graph, line graph, Mycielski's construction, k-critical graph, Four Color Theorem, Brooks' Theorem, edge coloring [Hamiltonian graph]

• Week 15 practice 15

  • 12/08 Necessary condition of Hamiltonicity, Dirac's Theorem

  • 12/10 Ore condition, Hamiltonian closure

• Week 16

  • 12/15

  • 12/17 Test 3

• 01/09 Instructor's deadline to upload scores