| Course Code: CS1216H Course Name: Elementary Graph Theory Prerequisites: Nil Syllabus: Graphs: definitions, types (simple, multigraphs, pseudographs, directed graphs), degree, adjacency, incidence, subgraphs, complements, walks, trails, paths, cycles, connected components, cut-vertices, bridges, blocks; Special graphs: complete, bipartite, regular, cycles, wheels, Petersen graph, hypercube; Trees: definitions, properties, unique path characterization, rooted trees, binary trees, spanning trees, Cayley`s formula (statement), block decomposition; Eulerian and Hamiltonian graphs: Euler`s theorem, necessary and sufficient conditions, Hamiltonian cycles, Dirac`s and Ore`s theorems (statements); Graph colouring: vertex colouring, chromatic number, chromatic polynomial (simple examples), Brooks` theorem, edge colouring, chromatic index; Matchings: matchings in bipartite graphs, Hall`s Marriage Theorem, perfect matchings, Tutte`s theorem (statement); Planarity: planar graphs, Euler`s formula, Kuratowski`s theorem (statement), non-planar graphs (K5, K3,3), Five Colour Theorem, Four Colour Theorem (statement); Extremal graph theory: Turan`s theorem (statement and bipartite case proof), forbidden subgraphs; Graph invariants: diameter, girth, radius, isomorphism. Texts: 1. Douglas B. West, Introduction to Graph Theory, 2nd Edition. Prentice Hall, 2001. 2. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. North-Holland, 1976. Available online: https://www.maths.ed.ac.uk/~v1ranick/papers/bondy.pdf |