MA2130 : Basic Graph Theory copy 2

Fundamentals:Graphs, subgraphs, isomorphism, representation of graphs, degrees and graphic sequences, walks, trails, Paths, Cycles, connectivity, bipartite graphs Trees: Characterisations of trees, minimum -spanning -trees, number of trees, cayley's formula connectivity: cut-seats, characterization of blocks. Search algorithms: DS,BFS, shortest peth algorithms, identification of cut-vertices and cut-edges. Eulerian and Hamilton graph; Characterizations, Necessary / sufficient conditions, Fleury's algorithms. Converings, independent sets:Basic relations, Matchings in bipartite graphs, Tutte's perfect matching theorem and consequences. Colorings, Edge-colorings of bipartite graphs, Gupta Vizing's theorem (without Proof), greedy algorithm for vertex-colorings, Brook's theorem, clique-number and vertex shromatic number. Planar graphs: Euler's formua V-E+F=2 and its consequences, Kuratowski's Characterization(without proof), DMP planarity algorithm. Direct graphs: Basics, various connectivities and tournaments.