# Graph Theory

By Dr.T.Asir   |   Madurai Kamaraj University
Learners enrolled: 962
The course on Graph Theory is a 4 credit course which contains 32 modules. This course deals with some basic concepts in graph theory like properties of standard graphs, Eulerian graphs, Hamiltonian graphs, Chordal graphs, Distances in graphs, Planar graphs, graph connectivity and Colouring of graphs. Further few graph Algorithms have also been discussed. This course is designed on par with the UGC syllabus.

The learners, as an outcome of successful completion will have a basic background of graph theory which has diverse applications in the areas of computer science, biology, chemistry, physics, sociology, and engineering.

Summary
 Course Status : Ongoing Course Type : Elective Duration : 12 weeks Start Date : 18 Jan 2023 End Date : 09 Apr 2023 Exam Date : Enrollment Ends : 12 Mar 2023 Category : Mathematics Credit Points : 4 Level : Undergraduate

### Course layout

Week- I

1. Introduction to graphs
2. Basic properties of graphs
3. Complete and bi-partite graphs

Week - II

4. Isomorphism of graphs
5. Paths and circuits

Week - III

6. Eulerian Graphs
7. Hamiltonian cycles

Week - IV

8.  Matrix representation of graphs
9.  Chordal graphs
10. Weighted graphs

Week - V

11. Matchings in graphs
12. Hall's 'marriage' theorem and its application
13. Travelling salesman’s problem & Chinese postman problem

Week - VI

14. Distances in graphs
15. Shortest path and Dijkstra’s algorithm
16. Floyd – Warshall Algorithm
17. Bellman-Ford Algorithm

Week - VII

18. Trees
19. Spanning tree in graphs

Week - VIII

20. Minimum spanning tree algorithms
21. Kruskal’s algorithm
22. Independence sets and covering in graphs

Week - IX

23. Planar graphs
24. Euler's formula

Week - X

25. Cut vertices and Cut edges
26. Edge connectivity

Week - XI

27. Vertex Colouring of graphs
28. Edge Colouring of graphs
29. The four-colour and five-colour theorems

Week - XII
30. Perfect Graphs
31. Applications of graphs in switching  theory
32. Directed Graphs (or Digraphs)

### Books and references

1. J. A. Bondy, and U.S.R. Murty, “Graph Theory”, Springer-Verlag, 2008

2. R. DIESTEL, “Graph Theory”, Springer-Verlag, 1997.

3. F. HARARY, “Graph Theory”, Addison-Wesley, 1969.

4. D.B. WEST, “Introduction to Graph Theory”, Prentice Hall, 1996.

5. R.J. WILSON, “Introduction to Graph Theory”, Longman, (3rd ed.) 1985

### Instructor bio 