What is Discrete Mathematical Structures (DMS) in VTU?

Discrete Mathematical Structures is a core VTU subject (course code BCS405A under the 2022 scheme) covering logic, set theory, relations, functions, combinatorics, recurrence relations and graph theory — the mathematical foundations of computer science.

What is the pigeonhole principle?

The pigeonhole principle states that if n+1 objects are placed into n boxes, then at least one box must contain two or more objects. Its generalised form: if N objects are placed into k boxes, at least one box contains ⌈N/k⌉ objects.

Discrete Mathematical Structures (DMS) Notes — VTU 2022 Scheme

Q: Which modules does the VTU 2022 DMS syllabus cover?

Module 1: Fundamentals of Logic. Module 2: Set Theory & Counting (including the pigeonhole principle). Module 3: Relations and Functions. Module 4: Recurrence Relations and Generating Functions. Module 5: Introduction to Graph Theory.

Discrete Mathematical Structures (DMS) is a foundational VTU course (course code BCS405A, 2022 scheme) for computer-science and engineering students. It develops the mathematical toolkit — logic, sets, relations, counting and graphs — that underpins algorithms, databases, cryptography and theoretical computer science. This page summarises the full syllabus and links to detailed branch-wise DMS notes hosted on the ATME resources portal.

VTU 2022 Scheme Syllabus — Module-wise

Module 1

Fundamentals of Logic

Propositions and logical connectives
Truth tables, tautologies and contradictions
Logical equivalence and laws of logic
Rules of inference and methods of proof
Quantifiers — universal and existential

Module 2

Set Theory & Counting (with Pigeonhole Principle)

Sets, subsets, power set, Venn diagrams
Set operations and Cartesian product
Rules of sum and product, permutations and combinations
Binomial theorem and combinations with repetition
The Pigeonhole Principle and its generalised form
Principle of Inclusion and Exclusion

Module 3

Relations and Functions

Cartesian products and relations
Properties: reflexive, symmetric, transitive
Equivalence relations and partitions
Partial orders, Hasse diagrams, lattices
Functions: one-to-one, onto, composition, inverse

Module 4

Recurrence Relations & Generating Functions

The first-order linear recurrence relation
Second-order linear homogeneous recurrence with constant coefficients
Non-homogeneous recurrence relations
Generating functions — definition and applications
Solving recurrences using generating functions

Module 5

Introduction to Graph Theory

Graphs, sub-graphs, complement, graph isomorphism
Euler trails and circuits, Hamilton paths and cycles
Planar graphs, Euler's formula
Trees — properties, spanning trees, minimum spanning trees
Graph colouring and chromatic polynomials

The Pigeonhole Principle — Quick Reference

One of the most elegant ideas in discrete mathematics and a frequent VTU exam topic.

Basic form

If n + 1 pigeons are placed into n pigeonholes, at least one hole contains two or more pigeons.

Generalised form

If N objects are placed into k boxes, some box contains at least ⌈N / k⌉ objects.

Classic example

Among any 13 people, at least two are born in the same month (13 people → 12 months → ⌈13/12⌉ = 2).

Discrete Mathematical Structures (DMS)