| Module | Topic | Details | Resources |
|---|---|---|---|
| 0 | Prerequisites | Proof Techniques Basics: Examples, Instructions and Exercises | slides[SDB], reference |
| 1 | Fundamental Concepts of graph theory | Graphs, isomorphism, subgraphs, matrix representations, degree, operations on graphs, degree sequences, Walks, trails, paths, connected graphs, distance, cut vertices, cut edges, blocks, weighted graphs, connectivity, Dijkstra’s shortest path algorithm, Floyd Warshall shortest path algorithm. | slides[SDB], all Exercises, marked Exercises |
| 2 | Tree Basics | Characterization of trees, rooted and binary trees, spanning trees and their properties, spanning trees in weighted graphs, minimum spanning tree, algorithms for minimum spanning tree. | slides[AVC], reference slides[SDB],all Exercises, marked Exercises |
| 3 | Graph Coloring and Matching | Coloring: Basic equations, matchings in bipartite graphs, perfect; Vertex-colourings; Chromatic number and cliques, greedy coloring algorithm, coloring of chordal graphs, Brook’s theorem; Edge colorings. | slides[SDB],all Exercises, marked Exercises |
| 4 | Planar graphs, Directed graphs | Basic concepts, Euler's formula for planar graphs, characterizations, planarity testing, 5-color-theorem; Directed graph, underlying graph, out-degree, indegree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments. | reference slides[SDB],all Exercises, marked Exercises |
| Coding Exercises | |||
| Sample Codes | Check out the python codes to start, need networx and matplotlib libraries | create_graphs, visualize_graphs, tree_construction, traversals, tree_properties, visualize_tree, animation_traversal | |
| Excercise 1 | From Module 1 | Graph Basics | |
| Excercise 2 | From Module 2 | Tree Basics | |
| Excercise 3 | From Module 3 | Coloring,Matching | |
| Excercise 4 | From Module 4 | Planarity,Connectivity | |
| Excercise 5 | Real-world Issues | Problems | |