Modules

Contents  (optional topics are indicated in red)

Number of lectures

Number of lectures by skipping 
optional topics

1 Preliminaries

Graphs,  isomorphism,  subgraphs,  matrix representations,  degree,  operations on graphs, degree sequences

5-10

4

2 Connected graphs and shortest paths

Walks, trails, paths, connected graphs, distance, cut-vertices, cut-edges, blocks, weighted graphs, connectivity, Dijkstra’s shortest path algorithm,  Floyd-Warshall  shortest path algorithm

4-8

4

3 Trees

Characterizations,  number of trees,  minimum spanning trees

5-10

4

4 Special classes of graphs

Bipartite graphs,  line graphs,  chordal  graphs

6-12

2

5 Eulerian graphs

Characterization,  Fleury’s algorithm,  chinese-postman-problem

2-4

2

6 Hamilton graphs

Necessary conditions and sufficient conditions

4-8

4

7 Independent sets, coverings and mathcings

Basic equations,  matchings in bipartite graphs, perfect matchings,  greedy and approximation algorithms

8-16

6

8 Vertex-colorings

Chromatic number and cliques,  greedy coloring algorithm,  coloring of chordal graphs,  Brook’s theorem

4-8

2

9 Edge-colorings

Gupta-Vizing theorem,  Class-1 graphs and class-2 graphs,  equitable edge-coloring

8-16

6

10 Planar graphs

Basic concepts,  Eulers formula,  polyhedrons and planar graphs,  charactrizations,  planarity testing,
5-color-theorem

10-20

3

11 Directed graphs

Directed graph,   underlying graph, out-degree,  in-degree,  connectivity,  orientation,  Eulerian directed graphs,  Hamilton directed graphs,  tournaments

8-16

6