Course Introduction

• Prerequisite：Mathematical maturity
• Recommended for： graduate students
• Introduction：

Graph is the model of many problems, e.g. computer programming, experimental designs, or even pure mathematical problems, and its theory is a delightful playground for the exploration of proof techniques in discrete mathematics. This course prepares students for algorithmic, constructive, probabilistic and algebraic abilities in dealing problems.

• Syllabus：

1. Fundamental Concepts: Definition, Graph Models, Some Graphs, Vertex degrees and Counting.
2. Matchings and Network Flow Problems: Maximum Network Flow, Minimum Cut Capacity, Duality, Ford-Fulkerson Theorem , Integral Flows, Hall’s Matching Theorem, Generalized Birkhoff's Theorem.
3. Coloring of Graphs: Definitions and Examples, Upper Bounds, Brook’ Theorem, Color-Critical Graphs, Szekeres-Wilf Theorem, Dirac Theorem, edge-colorings, König's Theorem, Vizing Theorem.
4. Connectivity: Connectivity, Edge-connectivity, k-connected Graphs, Whitney Theorem, Menger's Theorem.
5. Hamiltonian Graphs: Necessary Conditions, Ore Theorem, Chvátal-Erdös Theorem
6. Planar Graphs: Euler’s Formula, Five Color Theorem.
7. Ramsey Theory (optional): Ramsey’s Theorem, Graph Ramsey Theory
8. Extremal Graph Theory (optional): Mantel Theorem, Turán Theorem
9. Probabilistic Graph Theory (optional): Existence and Expectation, Properties of Almost All Graphs, Threshhold Functions
10. Linear Algebraic Graph Theory (optional): Eigenvalues and Graph Parameters, Eigenvalues of Regular Graphs, Strongly Regular Graphs.

• Reference：

1. Douglas B. West, Introduction to Graph Theory, Prentice Hall, 2001
2. J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001
3. Reinhard Diestel, Graph Theory, Electronic Edition, 2000