Discrete Structures and Graph Theory

Comprehensive Theory Notes for CBDT Assistant Director (Systems) Exam

1. Propositional Logic

Logical Connectives

Truth Table for Basic Connectives

Key Logical Equivalences

Types of Propositions

• Tautology: Always true (e.g., p ∨ ¬p)
• Contradiction: Always false (e.g., p ∧ ¬p)
• Contingency: Neither tautology nor contradiction
• Satisfiable: True for at least one assignment

Rules of Inference

2. Predicate Logic

A predicate is a statement containing variables that becomes a proposition when variables are assigned values.

Quantifiers

Negation Rules (Quantifiers)

• ¬∀x P(x) ≡ ∃x ¬P(x)
• ¬∃x P(x) ≡ ∀x ¬P(x)

Nested Quantifiers

• ∀x ∃y P(x,y): For every x, there exists a y (y can depend on x)
• ∃y ∀x P(x,y): There exists a single y that works for all x (stronger statement)
• Order matters: ∀x∃y ≠ ∃y∀x

Rules of Inference for Predicate Logic

3. Set Theory

Basic Definitions

• Set: Unordered collection of distinct elements
• Subset (A ⊆ B): Every element of A is in B
• Proper Subset (A ⊂ B): A ⊆ B and A ≠ B
• Power Set P(S): Set of all subsets of S; |P(S)| = 2^|S|
• Cardinality |S|: Number of elements in S

Set Operations

Set Identities

Key Formulas

• |A ∪ B| = |A| + |B| - |A ∩ B|
• |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |B∩C| - |A∩C| + |A∩B∩C|
• |A × B| = |A| × |B|
• |P(A)| = 2^|A|

4. Relations and Functions

Relations

A relation R from A to B is a subset of A × B.

Properties of Relations (on set A)

Types of Relations

Equivalence Relations and Classes

• Equivalence class [a] = {x ∈ A : (a,x) ∈ R}
• Equivalence classes partition the set (disjoint, cover entire set)

Functions

Function Composition

• (f ∘ g)(x) = f(g(x))
• Composition is associative but NOT commutative
• If f and g are bijective, then (f ∘ g)⁻¹ = g⁻¹ ∘ f⁻¹

Counting Relations

• Total relations from A to B: 2^(|A|×|B|)
• Reflexive relations on A (n elements): 2^(n²-n)
• Symmetric relations on A: 2^(n(n+1)/2)
• Equivalence relations on A: Bell number B(n)

5. Counting Principles

Basic Counting Rules

Permutations and Combinations

Key Identities

• C(n,r) = C(n, n-r)
• C(n,0) + C(n,1) + ... + C(n,n) = 2^n
• C(n,r) = C(n-1,r) + C(n-1,r-1) (Pascal's identity)
• P(n,n) = n!

Pigeonhole Principle

If n items are put into m containers and n > m, then at least one container must contain more than one item.

Generalized: If n items, m containers, then at least one container has ⌈n/m⌉ items.

Inclusion-Exclusion Principle

• |A ∪ B| = |A| + |B| - |A ∩ B|
• |A ∪ B ∪ C| = |A|+|B|+|C| - |A∩B|-|B∩C|-|A∩C| + |A∩B∩C|

6. Recurrence Relations

A recurrence relation defines a sequence recursively in terms of previous terms.

Common Recurrence Relations

Solving Linear Homogeneous Recurrence Relations

Form: aₙ = c₁·aₙ₋₁ + c₂·aₙ₋₂ + ... + cₖ·aₙ₋ₖ

Method:
1. Write characteristic equation: r^k - c₁·r^(k-1) - ... - cₖ = 0
2. Find roots r₁, r₂, ..., rₖ
3. Distinct roots: aₙ = A₁·r₁^n + A₂·r₂^n + ...
4. Repeated root (multiplicity m): Include terms with n^j·r^n for j=0,...,m-1
5. Use initial conditions to solve for constants

Master Theorem (for Divide and Conquer Recurrences)

T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1

Compare f(n) with n^(log_b(a)):

7. Graph Theory

Basic Definitions

• Graph G = (V, E): Set of vertices V and edges E
• Simple graph: No loops or multiple edges
• Multigraph: Allows multiple edges between vertices
• Pseudograph: Allows loops and multiple edges

Graph Terminology

Important Theorems

1. Handshaking Lemma: Σ deg(v) = 2|E| (sum of degrees = twice the edges)
2. In any graph, number of odd-degree vertices is even
3. Complete graph K_n: n(n-1)/2 edges (undirected), n(n-1) edges (directed)
4. Tree with n vertices: Exactly n-1 edges
5. Maximum edges in tree: n-1
6. Minimum edges for connected graph: n-1

Special Graphs

Graph Isomorphism

Two graphs G₁ and G₂ are isomorphic if there exists a bijection f: V₁ → V₂ such that (u,v) ∈ E₁ ⟺ (f(u),f(v)) ∈ E₂.

Necessary conditions for isomorphism (not sufficient):
- Same number of vertices
- Same number of edges
- Same degree sequence
- Same number of cycles of each length

Planar Graphs

A graph is planar if it can be drawn on a plane without edge crossings.

Euler's Formula (connected planar graph): V - E + F = 2
Where V = vertices, E = edges, F = faces (regions)

Key results:
- For simple planar graph: E ≤ 3V - 6 (if V ≥ 3)
- For bipartite planar graph: E ≤ 2V - 4
- K₅ and K₃,₃ are non-planar (Kuratowski's theorem)
- Every planar graph has a vertex of degree ≤ 5
- Four Color Theorem: Any planar graph can be colored with ≤ 4 colors

Graph Coloring

• Chromatic number χ(G): Minimum colors needed to color vertices such that no adjacent vertices share a color
• χ(G) ≤ Δ(G) + 1 (where Δ = maximum degree)
• Bipartite graphs: χ(G) = 2
• Complete graph K_n: χ(G) = n
• Cycle C_n: χ = 2 (even n), χ = 3 (odd n)
• Planar graphs: χ ≤ 4

Euler and Hamiltonian Paths/Cycles

Dirac's Theorem: If G has n ≥ 3 vertices and every vertex has degree ≥ n/2, then G has a Hamiltonian cycle.
Ore's Theorem: If for every pair of non-adjacent vertices, sum of degrees ≥ n, then G has a Hamiltonian cycle.

Trees and Spanning Trees

Spanning Tree: Subgraph that is a tree and includes all vertices of the original graph.

Properties:
- A connected graph with n vertices has a spanning tree with n-1 edges
- Number of spanning trees in K_n = n^(n-2) (Cayley's formula)
- Removing any edge from a spanning tree disconnects the graph

Minimum Spanning Tree (MST)

Kruskal's Algorithm:
1. Sort all edges by weight (ascending)
2. Add edge if it doesn't form a cycle (use Union-Find)
3. Stop when n-1 edges selected
- Time: O(E log E)

Prim's Algorithm:
1. Start from arbitrary vertex
2. Add minimum weight edge connecting tree to a new vertex
3. Repeat until all vertices included
- Time: O((V+E) log V) with min-heap

Shortest Path Algorithms

Dijkstra's Algorithm (Single Source, non-negative weights)

1. Set dist[source] = 0, others = ∞
2. While unvisited vertices exist:
   a. Pick unvisited vertex u with minimum dist[u]
   b. Mark u as visited
   c. For each neighbor v of u:
      alt = dist[u] + weight(u,v)
      if alt < dist[v]: dist[v] = alt

• Time: O((V+E) log V) with priority queue
• Does NOT work with negative weights

Bellman-Ford Algorithm (Single Source, handles negative weights)

1. Set dist[source] = 0, others = ∞
2. Repeat |V|-1 times:
   For each edge (u,v):
     if dist[u] + w(u,v) < dist[v]:
       dist[v] = dist[u] + w(u,v)
3. Check for negative cycles

• Time: O(V × E)
• Can detect negative weight cycles

Floyd-Warshall Algorithm (All-Pairs Shortest Path)

for k = 1 to V:
  for i = 1 to V:
    for j = 1 to V:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

• Time: O(V³)
• Space: O(V²)
• Works with negative weights (no negative cycles)

Graph Traversal

Applications of DFS:
- Topological sorting
- Finding strongly connected components (Kosaraju's, Tarjan's)
- Detecting cycles
- Finding bridges and articulation points
- Maze solving

Applications of BFS:
- Shortest path in unweighted graph
- Finding connected components
- Level-order traversal
- Web crawling

8. Posets and Lattices

Partially Ordered Set (Poset)

A set P with a binary relation ≤ that is:
- Reflexive: a ≤ a
- Antisymmetric: a ≤ b and b ≤ a → a = b
- Transitive: a ≤ b and b ≤ c → a ≤ c

Hasse Diagram

• Directed acyclic graph representing a poset
• Omit reflexive and transitive edges
• If a ≤ b, place b above a

Poset Terminology

Lattice

A poset where every pair of elements has both a supremum (join) and infimum (meet).

Properties:
- Commutative: a ∧ b = b ∧ a; a ∨ b = b ∨ a
- Associative: a ∧ (b ∧ c) = (a ∧ b) ∧ c
- Absorption: a ∧ (a ∨ b) = a; a ∨ (a ∧ b) = a
- Idempotent: a ∧ a = a; a ∨ a = a

Distributive Lattice: Meet distributes over join and vice versa.
Boolean Lattice: Distributive lattice with complement; models Boolean algebra.

Topological Sort

Linear ordering of vertices in a DAG such that if (u,v) is an edge, u appears before v.

Algorithms:
- Kahn's Algorithm (BFS): Repeatedly remove vertices with in-degree 0
- DFS-based: Reverse post-order of DFS

Time: O(V + E)

9. Group Theory Basics

A group (G, ) is a set G with a binary operation * satisfying:
1. Closure: a, b ∈ G → ab ∈ G
2. Associative: a(bc) = (ab)c
3. Identity: ∃e ∈ G: ae = ea = a
4. Inverse: ∀a ∈ G, ∃a⁻¹: a*a⁻¹ = e

If ab = ba for all a,b, the group is Abelian (commutative).

Examples of Groups

Subgroup H of G

• H ⊆ G
• H is closed under the operation
• Identity of G is in H
• Inverse of each element in H is in H

Lagrange's Theorem: Order of subgroup divides order of group.

Permutations and Combinatorics in Groups

• Symmetric group S_n: All permutations of n elements; order = n!
• Cyclic group: Generated by a single element
• Order of element a: Smallest positive k such that a^k = e

10. Generating Functions

A generating function is a power series that encodes a sequence.

Ordinary generating function: G(x) = Σ aₙ x^n

Useful generating functions:
| Sequence | Generating Function |
|----------|-------------------|
| 1, 1, 1, 1, ... | 1/(1-x) |
| 1, 2, 3, 4, ... | 1/(1-x)² |
| C(n,0), C(n,1), ..., C(n,n) | (1+x)^n |
| 1, r, r², r³, ... | 1/(1-rx) |
| Fibonacci | x/(1-x-x²) |

11. Key Theorems Summary

12. Exam Tips

• Handshaking lemma is almost always in exams: sum of degrees = 2E
• Euler path: exactly 0 or 2 vertices of odd degree; Euler circuit: all even
• Hamiltonian: no simple test; Dirac's and Ore's are sufficient (not necessary) conditions
• Planar graph: E ≤ 3V - 6; K₅ (5 vertices, 10 edges) and K₃,₃ are the basic non-planar graphs
• Chromatic number: χ(K_n) = n; χ(bipartite) = 2; χ(planar) ≤ 4
• BFS for shortest path in unweighted graphs; Dijkstra for weighted
• Bellman-Ford handles negative weights
• Floyd-Warshall is all-pairs shortest path: O(V³)
• Kruskal and Prim both find MST — know the difference
• Equivalence relation = reflexive + symmetric + transitive
• Partial order = reflexive + antisymmetric + transitive
• Cayley's formula: n^(n-2) spanning trees in K_n
• De Morgan's laws apply to both logic and sets
• Master theorem three cases must be clearly understood

Practice Questions

9 MCQs for Discrete Structures and Graph Theory with detailed explanations.

Q1. Consider the following about For every x, there exists a y (y can depend on x)

-...

- A. For every x, there exists a y (y can depend on x)

• B. It requires a minimum of O(n²) time complexity
• C. It applies only to sequential processing models
• D. It is not applicable in distributed systems

✅ Correct Answer: Option A

Explanation:
The correct answer is Option A — For every x, there exists a y (y can depend on x)
-.

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option B (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option C (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option D (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q2. Consider the following about Set Theory

Basic Definitions

• Set: Unordered colle...

• A. Set Theory

Basic Definitions

• Set: Unordered collection of distinct elements
• Subset (A ⊆ B): Every eleme
• B. It requires a minimum of O(n²) time complexity
• C. It applies only to sequential processing models
• D. It is not applicable in distributed systems

✅ Correct Answer: Option A

Explanation:
The correct answer is Option A — Set Theory

Basic Definitions

• Set: Unordered collection of distinct elements
• Subset (A ⊆ B): Every eleme.

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option B (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option C (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option D (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q3. Consider the following about Use initial conditions to solve for constants

Master Th...

• A. It is not applicable in distributed systems
• B. It requires a minimum of O(n²) time complexity
• C. Use initial conditions to solve for constants

Master Theorem (for Divide and Conquer Recurrences)

T(n) = aT(n/b)
- D.** It applies only to sequential processing models

✅ Correct Answer: Option C

Explanation:
The correct answer is Option C — Use initial conditions to solve for constants

Master Theorem (for Divide and Conquer Recurrences)

**T(n) = aT(n/b) .

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option A (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option B (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option D (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q4. Consider the following about Topological Sort

Linear ordering of vertices in a DAG su...

• A. It requires a minimum of O(n²) time complexity
• B. It applies only to sequential processing models
• C. Topological Sort
  Linear ordering of vertices in a DAG such that if (u,v) is an
• D. It is not applicable in distributed systems

✅ Correct Answer: Option C

Explanation:
The correct answer is Option C — Topological Sort
Linear ordering of vertices in a DAG such that if (u,v) is an.

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option A (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option B (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option D (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q5. Consider the following about Tautology:** Always true (e.g., p ∨ ¬p)...

• A. It is not applicable in distributed systems
• B. It requires a minimum of O(n²) time complexity
• C. It applies only to sequential processing models
• D. Tautology:** Always true (e.g., p ∨ ¬p)

✅ Correct Answer: Option D

Explanation:
The correct answer is Option D — Tautology:** Always true (e.g., p ∨ ¬p).

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option A (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option B (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option C (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q6. Consider the following about Contradiction:** Always false (e.g., p ∧ ¬p)...

• A. It applies only to sequential processing models
• B. It is not applicable in distributed systems
• C. It requires a minimum of O(n²) time complexity
• D. Contradiction:** Always false (e.g., p ∧ ¬p)

✅ Correct Answer: Option D

Explanation:
The correct answer is Option D — Contradiction:** Always false (e.g., p ∧ ¬p).

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option A (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option B (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option C (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q7. Consider the following about Contingency:** Neither tautology nor contradiction...

• A. It applies only to sequential processing models
• B. Contingency:** Neither tautology nor contradiction
• C. It is not applicable in distributed systems
• D. It requires a minimum of O(n²) time complexity

✅ Correct Answer: Option B

Explanation:
The correct answer is Option B — Contingency:** Neither tautology nor contradiction.

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option A (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option C (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option D (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q8. Consider the following about Satisfiable:** True for at least one assignment...

• A. Satisfiable:** True for at least one assignment
• B. It applies only to sequential processing models
• C. It requires a minimum of O(n²) time complexity
• D. It is not applicable in distributed systems

✅ Correct Answer: Option A

Explanation:
The correct answer is Option A — Satisfiable:** True for at least one assignment.

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option B (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option C (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option D (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.

Q9. Consider the following about Order matters: ∀x∃y ≠ ∃y∀x...

• A. It requires a minimum of O(n²) time complexity
• B. It applies only to sequential processing models
• C. It is not applicable in distributed systems
• D. Order matters: ∀x∃y ≠ ∃y∀x

✅ Correct Answer: Option D

Explanation:
The correct answer is Option D — Order matters: ∀x∃y ≠ ∃y∀x.

This is a standard concept in Discrete Structures and Graph Theory. The answer follows from the fundamental definitions and properties covered in this topic.

Why other options are incorrect:
- Option A (It requires a minimum of O(n²) time complexity...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option B (It applies only to sequential processing models...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.
- Option C (It is not applicable in distributed systems...) — This does not correctly answer the question as it either misstates the concept or refers to a different context.