| Description |
Review of elementary graph theory. Trees. Matrix-tree theorem. Enumerating spanning trees of a graph. Graph decompositions. Connectivity and k-connectivity of graphs. Disjoint paths and connectivity of graphs. Menger’s and Whitney’s theorems. Graph assembling and disassembling of 3-connected and quasi 4-connected graphs. Various Euler problems. Hamiltonian cycles. The k-closure of a graph. Bondy-Chvátal’s theorem. Long cycles in a graph. Dirac’s theorem. Factors. Maximum and perfect matchings. Tutte’s and Edmonds-Gallai’s theorems. Berge-Tutte duality theorem. Perfect graphs. Lovász’ theorem. Edge colorings. Vizing’s theorem. Independent sets and cliques. Vertex colorings. Brook’s theorem. Embeddings of graphs in the plane. Kuratowski’s, Whitney’s, MacLane’s, and Kelmans’ planarity criteria. Five-colour and four-colour theorems on planar graphs. On the hamiltonicity of planar graphs. |