Lesson 11 — Intermediate

Graph Theory Basics

Graph theory discrete maths ka sabse visual aur practical topic hai — stations aur tracks, users aur friendships, sab graph hain. Is lesson mein seekhenge graph kya hota hai, degree aur handshaking lemma, types of graphs, aur Euler circuit ki condition. GATE ka sabse scoring section yahi hai.

Graph kya hai

Ek graph ka size do numbers se banta hai: |V| (vertices) aur |E| (edges). Degree = har vertex ki incident edges ki ginti. Inhi numbers se aage ke sare formulas bante hain.

Degree aur Handshaking Lemma

Degree deg(v) = vertex ki incident edges ki ginti

Handshaking Lemma (GATE ka favourite):
  Σ deg(v) = 2|E|
  (har edge do vertices ko touch karti hai — 2 baar count)

Worked: 4 vertices, har ka degree 3 (yaani K4)
  Σ deg = 4 × 3 = 12  ⇒  |E| = 12 / 2 = 6  ✓

Directed graph mein:
  out-degree + in-degree = poora degree
  Σ out-deg = Σ in-deg = |E|

Corollary: odd degree wale vertices HAMESHA even
sankhya mein hote hain (ka total even rehna chahiye)

Graph ke types

Types (GATE classification):
Simple graph   : no loop, no parallel edge
Multigraph     : parallel edges (do edges same pair pe)
Pseudograph    : loops + parallel edges dono
Weighted graph : edges pe number (distance, cost)

Complete graph K_n : har do vertices directly connected
  |E| = n(n−1)/2     K4 = 6 edges,  K5 = 10 edges

Regular graph : har vertex ka same degree (k-regular)
Bipartite     : V do groups mein, sirf cross-group edges
Complete bipartite K(m, n) : m × n edges
Planar graph  : plane mein bina edges cross kiye draw

Complete graph ka formula rat lo — n(n−1)/2. K5 = 10 edges ye har saal kahin na kahin aata hai. Bipartite graph theoretical questions (2-coloring) mein bhi aata hai.

Paths, cycles aur Euler graphs

• Path: bina vertex repeat kiye edges ka rasta. Simple path: vertices bhi repeat nahi.
• Cycle: path jiska start vertex = end vertex.
• Connected graph: har do vertices ke beech path ho.
• Complete bipartite: K(m,n) mein m×n edges — har ek m wale ko har ek n wale se jodta hai.

Adjacency Matrix (undirected graph → symmetric):
     a b c
a  [ 0 1 1 ]
b  [ 1 0 1 ]
c  [ 1 1 0 ]   → 3 edges,  har row ka sum = degree = 2

EULER graph : ek trail mein sab edges (bina repeat kiye)
  Condition : connected + HAR vertex ka EVEN degree
  (Königsberg bridge problem — graph theory ki shuruat)

HAMILTONIAN : sab vertices EK BAAR (edges repeat allowed nahi)
  Koi aasan fixed condition nahi — NP-complete problem

Exercise

Common mistakes

• Handshaking mein 2 chhod dena: Σ deg = 2|E| — har edge do baar count hoti hai (dono endpoints). Deg ka seedha sum = edges mat likho, divide by 2 karna zaroori hai.
• Euler aur Hamiltonian mix: Euler = EDGES ek baar (degree condition se), Hamiltonian = VERTICES ek baar (koi easy condition nahi). Ye do alag cheezein hain.
• Directed degree ko simple ginna: Digraph mein in-degree aur out-degree alag alag. Σ out-deg = Σ in-deg = |E| — ye relation exam mein aata hai.

Vertices : major stations (Delhi, Howrah, Chennai...)
Edges    : direct train routes
Degree   : Howrah jaisa junction = high degree node
Cycle    : Mumbai se Pune se Nagpur... wapas = ring route
Question : Delhi se Chennai shortest path = graph algorithm