PYQ coming soon
EXAMhelp · GATE notes
Discrete Mathematics
CH 01Sets, relations, graphs
Key points
- Relations on an n-element set: 2^(n²). Reflexive relations: 2^(n² − n).
- Symmetric relations: 2^(n(n+1)/2).
- Sum of degrees in any graph = 2 × number of edges.
- A tree with n vertices has n − 1 edges.
- Euler circuit exists iff the graph is connected and every vertex has even degree.
- Planar graph (connected): V − E + F = 2.
Formulas & facts
- Functions A → B (|A| = m, |B| = n)
- nᵐ
- Derangements Dₙ
- n! Σ (−1)ᵏ / k!
- Labelled trees on n vertices
- n^(n − 2)