Graph Theory

Lectures:

1) Graphs, simple graphs. Graph isomorphisms. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex. Paths and cycles.
2) Trees, bridges and cuts. Connectivity and blocks.
3) Matching and covers in general and bipartite graphs. Perfect matchings.
4) Edge colorings. Chromatic index, Vizing's Theorem.
5) Vertex colorings, Chromatic number, Brook's Theorem.
6) Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Folor Theorem.
7) Eulerian and Hamiltonian graphs.
8) Oriented graphs. Oriented paths and cycles.
9) Flows in networks, cuts. Maximal flow and minimal cut Theorem.



Discussions:

1) Graphs, simple graphs. Degree of a vertex. Paths and cycles. Important graph classes.
2) Trees, bridges and cuts. Connectivity, blocks and articulations.
3) Graph connectivity.
4) Matching and covers in general and bipartite graphs. Perfect matchings.
5) Edge colorings. Chromatic index.
6) Vertex colorings, Chromatic number.
7) Planar graphs. Euler's formula for general planar graphs.
8) Eulerian and Hamiltonian graphs.
9) Oriented graphs. Oriented paths and cycles.