Discrete Mathematics: Graph Theory & Recurrence Relations

Identify fundamental graph properties (degree sequence, bipartiteness) and apply the Handshaking Lemma.

Find connected components, cut vertices, and cut edges in a graph using Depth-First Search (DFS) traversal.

Determine if a given graph contains an Eulerian path/circuit or a Hamiltonian cycle.

Analyze the properties of trees and calculate the number of spanning trees in a graph using matrix tree theorem or Cayley's formula.

Find a maximum matching in a bipartite graph using algorithms like Hopcroft-Karp or augmenting paths.

Compute the chromatic number of simple graphs and apply theorems like Brooks' and the Five Color Theorem for planar graphs.

Solve linear homogeneous and non-homogeneous recurrence relations with constant coefficients.

Formulate and use ordinary generating functions to solve recurrence relations and counting problems.