GRAPH THEORY

A graph G = (V, E) consists of vertices (nodes) V and edges E connecting pairs of vertices.

Types of graphs:

Undirected (edges are unordered pairs) vs directed (digraph) (ordered pairs).
Weighted (each edge has a value) vs unweighted.
Simple (no self-loops, no parallel edges) vs multigraph.
Complete graph K_n: every pair of vertices connected. K_n has C(n,2) = n(n-1)/2 edges.
Bipartite: vertices split into two sets; edges only between sets, not within.
Tree: connected acyclic graph. n vertices → exactly n-1 edges.

DEGREE OF A VERTEX = number of edges incident on it.

For directed graphs: in-degree + out-degree.

Handshaking lemma: sum of all vertex degrees = 2 × number of edges.

Corollary: number of odd-degree vertices is even.

GRAPH REPRESENTATIONS

1. Adjacency matrix: n×n matrix where A[i][j] = 1 if edge from i to j.

Space O(n²).
Edge check: O(1).
Enumerate neighbours: O(n).
Best when graph is dense.

2. Adjacency list: each vertex has a list of its neighbors.

Space O(n + m) where m = number of edges.
Edge check: O(degree).
Enumerate neighbours: O(degree).
Best when graph is sparse.

EULER vs HAMILTONIAN

Euler path/circuit: uses every EDGE exactly once.

Euler circuit exists iff graph is connected AND all vertices have even degree.
Euler path (not circuit) exists iff exactly 2 vertices have odd degree.
Königsberg bridges problem (Euler, 1736) — birth of graph theory.

Hamiltonian path/circuit: visits every VERTEX exactly once.

No simple characterization. NP-complete to decide.

ISOMORPHISM

Two graphs are isomorphic if there's a bijection between their vertex sets that preserves edges.

Necessary conditions (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 without crossing edges.

Euler's formula for planar graphs: V − E + F = 2 (where F = number of faces, including outer).

Kuratowski's theorem: a graph is non-planar iff it contains a subdivision of K₅ (complete on 5 vertices) or K_{3,3} (complete bipartite with 3+3 vertices).

GRAPH COLORING

Chromatic number χ(G): minimum colors needed so no two adjacent vertices have same color.

For a tree: χ = 2.
For an odd cycle: χ = 3.
For K_n: χ = n.

Four color theorem (1976): every planar graph has χ ≤ 4. First major theorem proved by computer.

TREES

A tree is connected, acyclic graph.

Properties:

n vertices → n − 1 edges.
Unique path between any two vertices.
Adding any edge → exactly one cycle.
Removing any edge → disconnects.

Spanning tree: subgraph containing all vertices, that is a tree.

Cayley's formula: number of distinct labeled trees on n vertices = n^(n-2).

SHORTEST PATH / MST / FLOW (covered separately in algorithms chapter — Pack 3).

SET THEORY essentials:

A ∪ B (union)
A ∩ B (intersection)
A − B = A ∩ B' (difference)
A × B = {(a, b) : a ∈ A, b ∈ B} (Cartesian product)
Power set P(A): all subsets of A. |P(A)| = 2^|A|.

Inclusion-Exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|.

For 3 sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|.

FUNCTIONS / RELATIONS (covered in Pack 1).

COMBINATORICS (covered in Pack 2):

nPr, nCr, multinomial, Pigeonhole principle.

Recurrence relations:

T(n) = aT(n-k) + f(n) for some constants.

Solved by characteristic equation method, generating functions, or master theorem.

GENERATING FUNCTIONS:

A power series whose coefficients encode a sequence. Useful for solving recurrences and counting problems.

Example: Fibonacci. F(x) = x / (1 − x − x²).

Key counting principles for GATE:

Multiplication: if step 1 has m choices, step 2 has n, total = m × n.
Addition: if disjoint choices m or n, total = m + n.
Permutations with repetition: n^r.
Stars and bars: distributing n identical items into k distinct boxes: C(n + k − 1, k − 1).

Discrete Mathematics

Graph theory basics