DISCRETE MATHEMATICS AND GRAPH THEORY

UNIT-I: Mathematical Logic and Set Theory (08 Hrs)
Propositions and Logical Operations, Quantifiers, Conditional Statements and
Tautologies, Methods of Proof, Principle of Mathematical Induction. Basic
concepts of set theory, Operations on Sets, The power set.
UNIT-II: Relations and Functions (12 Hrs)
Relations: Ordered pairs and n-tuples, Product Sets and Partitions, Relations and
Digraphs, Matrix of Relation, Paths in Relations and Digraphs, Properties of
Relations, Equivalence Relations & Partitions, Compatible Relation, Manipulation
of Relations, Composition of Relations, Transitive Closure of a relation, Partial
order relation, Partially ordered set, Hasse Diagrams. Functions: Definition,
Composition of functions, Types of Functions, Invertible Function, Permutation
Function, Characteristics function of a set with Theorems.
UNIT-III: Group Theory (12 Hrs)
Binary Operations, Properties, Semigroups, Monoids,Subsemigroup,Submonoid,
Isomorphism & Homomorphism, , Groups (only definitions and examples)
Subgroups and Homomorphism, Cosets and Lagrange’s Theorem, Normal
subgroups.
Unit- IV:Rings, Lattices & Boolean Algebra(10 Hrs)
Rings, Fields, Integral Domain, Ring Homomorphism (definitions & examples),
Lattices: Properties, Types of Lattices, Sub lattices, Isomorphic Lattices,
Complemented & Modular Lattices (definitions & examples), Boolean Algebra:
Definition, Properties, Simplification of Switching Circuits.
Unit-V: Graph Theory (12 Hrs)
Basic concepts of Graph Theory, Digraphs, Basic definitions, Paths and Circuits,
Reachability and Connectedness, Matrix representation of graphs, Subgraphs&
Quotient Graphs, Isomorphic digraphs & Transitive Closure digraph, Euler’s Path
& Circuit (only definitions and examples). Trees, Binary Tree, Labeled Trees,
Undirected Trees, Spanning Trees of Connected Relations, Prim’s Algorithm to

construct Spanning Trees, Weighted Graphs, Minimal Spanning Trees by Prim’s
Algorithm &Kruskal’s Algorithm.

Unit-VI: Combinatorics(06 Hrs)
Generating Functions, Recurrence Relations, Counting: Permutations &
Combinations, Pigeonhole Principle with Simple Applications.
Text Books
1. Discrete Mathematical Structures(3rd Edition) by Kolman, Busby & Ross
PHI.
2. Discrete Mathematical Structures with Applications to Computer Science by
Tremblay &Manohar, Tata McGraw- Hill.
3. Combinatorial Mathematics, C.L. Liu (McGraw Hill)
Reference Books
1. Discrete Maths for Computer Scientists & Mathematicians by Mott,
Kandel, Baker.
2. Elements of Discrete Mathematics by C. L. Liu.
3. Discrete Mathematics by Lipschutz.
4. Discrete Mathematics by R.Johnsonbaugh.
5. Higher Engineering Mathematics by B.S. Grewal, 40th Edition, Khanna
Publication