Discrete Mathematics & Graph Theory

Propositional calculus: statements and notations, connectives, well-formed formula, truth tables; Tautologies, equivalence of formulas, duality law, tautological implications, normal forms; Theory of inference for statement calculus: consistency of premises, indirect method of proof; Predicate calculus: predicates, statement functions, variables and quantifiers, free and bound variables, inference theory

Sets: operations on sets, principle of inclusion-exclusion; Relations: properties, operations, partition and covering, transitive closure; Equivalence, compatibility and partial ordering, Hasse diagrams; Functions: bijective, composition, inverse, permutation and recursive functions; lattice and its properties

Basis of counting; permutations with repetition, circular and restricted permutations; Combinations, restricted combinations; binomial and multinomial coefficients and theorems; Recurrence relations: generating functions, function of sequences, partial fractions, calculating coefficients; Formulation as recurrence relations; solving by substitution and generating functions; method of characteristic roots; inhomogeneous relations

Basic concepts, graph theory and its applications, subgraphs; Graph representations: adjacency and incidence matrices; Isomorphic graphs, paths and circuits; Eulerian and Hamiltonian graphs

Multigraphs, bipartite and planar graphs, Euler's theorem; Graph colouring and covering, chromatic number; Spanning trees, Prim's and Kruskal's algorithms; BFS and DFS spanning trees