Notes / GATE / Discrete Mathematics

CH 01

Sets, relations, graphs

Discrete Mathematics · GATE

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)
Done with this chapter? Now put it to use.Today's GATE question →