Graph Theory Notes & Formulas

1. Definition

Study of graphs G = (V, E) - vertices (nodes) connected by edges. Models networks, relationships, and paths.

2. Basic Terminology (Very Important)

• Degree: Number of edges incident to a vertex. deg(v) = number of neighbors
• Handshaking Lemma: Σ deg(v) = 2|E| → sum of degrees always even → number of odd-degree vertices is always even
• Simple graph: No self-loops, no multiple edges
• Complete graph Kₙ: Every pair connected. Edges = n(n−1)/2

3. Types of Graphs

| Type | Property |
|---|---|
| Connected | Path exists between every pair of vertices |
| Bipartite | Vertices split into two sets, edges only between sets |
| Complete bipartite Km,n | Every vertex in set 1 connected to every vertex in set 2 |
| Tree | Connected + acyclic. Edges = n−1 for n vertices |
| Forest | Acyclic (collection of trees) |
| Planar | Can be drawn without edge crossings |

4. Trees (Very Important)

For a tree with n vertices:

• Exactly n−1 edges
• Exactly one path between any two vertices
• Removing any edge disconnects it
• Adding any edge creates exactly one cycle
• Number of labeled trees on n vertices = nⁿ⁻² (Cayley's formula)

5. Graph Traversals

BFS (Breadth First Search): Uses queue. Finds shortest path in unweighted graph. Time: O(V+E)
DFS (Depth First Search): Uses stack/recursion. Used for cycle detection, topological sort. Time: O(V+E)

6. Euler & Hamilton (Very Important)

Eulerian Path/Circuit (visits every EDGE exactly once):

• Eulerian circuit exists iff graph is connected and every vertex has even degree
• Eulerian path exists iff exactly 2 vertices have odd degree

Hamiltonian Path/Circuit (visits every VERTEX exactly once):

• No simple necessary and sufficient condition (NP-complete problem)
• Dirac's condition: Every vertex degree ≥ n/2 → Hamiltonian circuit exists

7. Planar Graphs

Euler's formula: V − E + F = 2 (V=vertices, E=edges, F=faces including outer face)

• For simple planar graph: E ≤ 3V − 6
• For bipartite planar graph: E ≤ 2V − 4
• K₅ and K₃,₃ are the minimal non-planar graphs (Kuratowski's theorem)

8. Graph Coloring

• Chromatic number χ(G): Minimum colors to color vertices so no two adjacent vertices share a color
• χ(Kₙ) = n, χ(bipartite) = 2 (if non-empty), χ(odd cycle) = 3, χ(even cycle) = 2
• Four Color Theorem: Any planar graph → χ ≤ 4

9. Shortest Path & Spanning Tree

• Dijkstra's: Single-source shortest path, non-negative weights. O(V²) or O(E log V)
• Bellman-Ford: Handles negative weights. O(VE)
• Kruskal's / Prim's: Minimum spanning tree. O(E log V)
• MST weight is unique even if MST is not

10. GATE Trick

Handshaking lemma instantly eliminates invalid graph configurations. Eulerian circuit conditions (all even degree) are directly tested. Euler's formula V−E+F=2 combined with E≤3V−6 is used to prove non-planarity. For cycle detection: DFS back edge → cycle exists.