Graph Theory Practice Questions

### 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.