Course information

Introduction: Basic terminology. Vertex Degrees: Properties. Vertex-degree sequences (the Havel-Hakimi and the Erdos-Gallai theorems). Vertex-degree sets (the Kapoor-Polimeni-Wall theorem). Paths, Circles, Distances: Definitions and properties. Eccentricity. Distance decomposition. Graph circumference and graph girth. Graph Connectivity: Vertex connectivity, minimum separators, properties of connected graphs. Biconnectivity, k-connectivity (Menger theorem, Whitney theorem, Halin theorem). Edge connectivity. Trees: Definitions and basic properties. Spanning tree. Labeled tree. Prufer sequence. Cayley’s theorem. Eulerian Graphs: Euler tour and Euler path. Characterization of Eulerian graphs. Fleury’s algorithm. Euler’s theorem. The Chinese-postman problem. Hamiltonian Graphs: Definitions and properties. Dirac’s theorem. Ore’s theorem. Bondy-Chvatal theorem. Vertex Coloring: k-coloring, chromatic number. Brook’s theorem. Matchings: Maximum and perfect matchings, alternating and augmenting paths. Berge’s theorem. Bipartite matchings. Hall’s theorem. Edge Coloring: k-edge coloring, chromatic index. Properties. Planar Graphs: Definitions and properties. Euler’s theorem. Kuratowski’s theorem. Outerplanar graphs. Coloring of planar graphs.