Skip to content

🧮 Discrete Mathematics and Graph Theory (105304)

⬅️ Back to Semester-3 | 🏠 Home

💡 Why this subject? This is the math behind algorithm correctness proofs, database design, cryptography, and the Graph unit directly powers your DSA Graph topics.

📌 Unit 1: Sets, Relation and Function

  • Set operations: Union (∪), Intersection (∩), Difference (-), Complement.
  • Cartesian Product: A × B = all ordered pairs (a,b) where a∈A, b∈B.
  • Relation: a subset of A × B — basically a set of connections between elements.
  • Equivalence Relation: Reflexive + Symmetric + Transitive (e.g., "has the same birthday month as").
  • Partial Ordering: Reflexive + Antisymmetric + Transitive (e.g., "divides," "≤").
  • Bijective function: both one-to-one (injective) AND onto (surjective) — has a perfect inverse.
  • Countable vs Uncountable sets: Countable = can be listed (even if infinite, like integers). Uncountable = can't (like real numbers) — proved by Cantor's diagonal argument.

📝 Example: Database foreign keys rely on relations; hash functions rely on functions being well-defined (each input → exactly one output).

📌 Unit 2: Mathematical Induction & Counting

  • Mathematical Induction: prove a statement for all natural numbers by (1) proving the base case, (2) assuming it's true for n=k, (3) proving it then holds for n=k+1.
  • Well-Ordering Principle: every non-empty set of positive integers has a least element — the foundation that makes induction valid.
  • Division Algorithm: a = bq + r (0 ≤ r < b) — basis of the modulo operator % in programming!
  • Euclidean Algorithm: fastest way to find GCD of two numbers.
  • Pigeonhole Principle: if you put n+1 items into n boxes, at least one box has ≥2 items. Sounds obvious but proves surprisingly deep results (e.g., two people in a city share a birthday).
  • Permutations & Combinations:
  • Permutation (order matters): nPr = n!/(n-r)!
  • Combination (order doesn't matter): nCr = n!/(r!(n-r)!)

📝 Example — Induction proving a sum formula: 

Claim: 1 + 2 + ... + n = n(n+1)/2
Base case (n=1): 1 = 1(2)/2 = 1 ✓
Inductive step: assume true for n=k, prove for n=k+1
  1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓

🧠 Quick Recall: Euclidean Algorithm is literally what gcd() library functions use under the hood — gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0) = 6.

📌 Unit 3: Propositional Logic

  • Connectives: AND (∧), OR (∨), NOT (¬), Implication (→), Biconditional (↔).
  • Truth Table: lists output for every input combination.
  • Logical Equivalence: De Morgan's Laws are the most-used:
  • ¬(A∧B) = ¬A ∨ ¬B
  • ¬(A∨B) = ¬A ∧ ¬B
  • Rules of Inference: e.g., Modus Ponens — if A→B is true and A is true, then B is true.
  • Quantifiers: ∀ (for all), ∃ (there exists).

📝 Example — programming connection: if (!(a && b)) in code is literally De Morgan's law: !(a && b) == (!a || !b) — compilers and good programmers use this to simplify conditions.

📌 Unit 4: Proof Techniques

  • Forward Proof: start from given facts, derive the conclusion step by step.
  • Proof by Contradiction: assume the opposite of what you want to prove, show it leads to something impossible.
  • Proof by Contraposition: to prove A→B, instead prove ¬B→¬A (logically equivalent, sometimes easier).

📝 Classic example — √2 is irrational (proof by contradiction): Assume √2 = p/q (in lowest terms) → leads to both p and q being even → contradicts "lowest terms" → so √2 must be irrational.

📌 Unit 5: Algebraic Structures and Morphism

  • Semigroup: set + associative binary operation.
  • Monoid: semigroup + identity element.
  • Group: monoid + every element has an inverse.
  • Ring: set with two operations (+ and ×) satisfying group/distributive properties.
  • Boolean Algebra: algebra over {0,1} with AND/OR/NOT — directly the math behind Digital Electronics & programming logic!

🧠 Quick Recall: Group hierarchy: Semigroup ⊂ Monoid ⊂ Group — each adds one more property (associativity → identity → inverses).

📝 Example: Integers under addition form a Group (identity=0, inverse of n is -n). Integers under multiplication are only a Monoid (identity=1, but no inverse for most numbers — 1/3 isn't an integer).

📌 Unit 6: Graphs and Trees ⭐ (directly used in DSA!)

  • Graph properties: Degree (number of edges at a vertex), Connectivity, Path, Cycle.
  • Isomorphism: two graphs that are "structurally the same" even if drawn differently.
  • Eulerian Walk: visits every edge exactly once. Hamiltonian Walk: visits every vertex exactly once.
  • Graph Coloring: assign colors to vertices so no two adjacent vertices share a color — used in scheduling, map coloring, register allocation in compilers!
  • Planar Graph: can be drawn without edges crossing.
  • Trees: a connected graph with no cycles. Rooted tree: has one designated root (exactly what you use in DSA's Binary Trees!).
  • Weighted trees & prefix codes: e.g., Huffman coding (used in file compression) builds an optimal prefix-code tree.
  • Articulation Points: a vertex whose removal disconnects the graph — critical in network reliability analysis.
  • Shortest distances: foundation for algorithms like Dijkstra's (covered practically in DSA).

📝 Example: Exam timetable scheduling = graph coloring problem (subjects with common students = connected, must get different "color" = time slot).

✅ Quick Revision Table

Topic One-line memory hook
Equivalence relation Reflexive + Symmetric + Transitive
Pigeonhole Principle n+1 items, n boxes → one box has ≥2
Euclidean Algorithm Fast GCD — basis of gcd() functions
De Morgan's Law !(a&&b) == (!a \|\| !b)
Proof by contradiction Assume opposite, find impossible result
Group Monoid + every element has an inverse
Eulerian vs Hamiltonian Every edge once vs every vertex once
Graph coloring No two adjacent vertices share a color