# KTU Study Materials Graph Theory and Combinatorics S5 CS

### KTU Graph Theory Notes PDF CS 309

Introductory concepts - What is graph – Application of graphs – finite and infinite graphs – Incidence and Degree– Isolated vertex, pendent vertex and Null graph. Paths and circuits – Isomorphism, sub graphs, walks, paths and circuits, Connected graphs, disconnect graphs.

Euler graphs, Hamiltonian paths and circuits, Dirac's theorem for Hamiltonicity, Travelling salesman problem.Directed graphs – types of digraphs,Digraphs and binary relation Trees – properties, pendent vertex, Distance and centres -Rooted and binary tree, counting trees, spanning trees.

Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices, Fundamental circuits, Planar graphs, Different representation of planar graphs, Euler's theorem, Geometric dual, Combinatorial dual.

Matrix representation of graphs- Adjacency matrix, Incidence Matrix, Circuit matrix, Fundamental Circuit matrix and Rank, Cut set matrix, Path matrix

Graphs theoretic algorithms - Algorithm for  computer   representation of a graph, algorithm for connectedness and components, spanning tree, shortest path.

Part-1

Part-2