Reminder

• Distinguish closed walk and cycle

• Whenever write a statement, always think about edge case (e.g., n=2)

Graph Theory Convention

• Independence number $\alpha(G)$
• Maximum degree $\Delta(G)$, minimum degree $\delta(G)$
• Maximum matching $\alpha’(G)$
• minimum VC size $\beta(G)$, minimum EC size $\beta'(G)$
• the number of odd components $o(G)$
• Connectivity $\kappa(G)$, edge connectivity $\kappa'(G)$
• Chromatic number $\chi(G)$
• Clique number $\omega(G)$

Ch1 Fundamental Concepts

Ch2 Trees and Distance

Ch3 Matching and Factors

Ch4 Connectivity and Paths

Ch5 Coloring of Graphs

Vertex Coloring