Questions
~2 questions per paper
Difficulty
Medium
Importance
Medium yield for PSU technical sections
Overview
Graph Theory is a fundamental branch of discrete mathematics that models pairwise relations between objects using vertices and edges. For Indian PSU exams, understanding connectivity, traversability, and tree properties is essential for solving algorithmic and network-based problems. Mastering these concepts provides a competitive edge as they frequently appear in technical aptitude sections.
Connectivity and Components
A graph is connected if there is a path between every pair of vertices, and a component is a maximal connected subgraph. In exams, you must distinguish between vertex connectivity and edge connectivity to identify bottleneck vulnerabilities in networks.
- A graph with n vertices and fewer than n-1 edges is always disconnected.
- Vertex connectivity k(G) is the minimum vertices to remove to disconnect the graph.
- Edge connectivity λ(G) is the minimum edges to remove to disconnect the graph.
- Whitney's Theorem: k(G) ≤ λ(G) ≤ degree(min_vertex).
- A complete graph K_n has k(G) = n-1.
Trees and Spanning Trees
Trees are acyclic, connected graphs that serve as the backbone for various network routing algorithms. A spanning tree is a subgraph that includes all vertices of the original graph without cycles.
- A tree with n vertices always has exactly n-1 edges.
- Cayley's Formula: Number of spanning trees for K_n is n^(n-2).
- A graph is a tree if and only if it is minimally connected.
- Every connected graph has at least one spanning tree.
- Sum of degrees of all vertices in a tree is 2(n-1).
Euler and Hamiltonian Graphs
Eulerian graphs deal with traversing all edges exactly once, while Hamiltonian graphs concern visiting every vertex exactly once. These are classic topics for PSU exams involving circuit design and routing efficiency.
- Eulerian Circuit exists if the graph is connected and every vertex has an even degree.
- Eulerian Path exists if exactly zero or two vertices have an odd degree.
- Hamiltonian path visits each vertex exactly once.
- Dirac's Theorem: If degree(v) ≥ n/2 for every vertex, the graph is Hamiltonian.
- Ore's Theorem: If deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices, the graph is Hamiltonian.
Graph Coloring
Graph coloring involves assigning colors to vertices such that no two adjacent vertices share the same color. The minimum number of colors required is known as the chromatic number, denoted by χ(G).
- χ(G) = 1 for a null graph.
- χ(G) = 2 if and only if the graph is bipartite.
- χ(G) = n for a complete graph K_n.
- Four Color Theorem: Every planar graph is 4-colorable.
- Brook's Theorem: χ(G) ≤ Δ(G) + 1 (where Δ is maximum degree).
Formula Sheet
Handshaking Lemma: sum(deg(v)) = 2 * |E|
Number of edges in K_n: n(n-1)/2
Cayley's Formula: n^(n-2)
Euler's Formula for planar graphs: V - E + F = 2
Exam Tip
Always verify if a graph is bipartite before attempting to calculate the chromatic number, as χ(G)=2 simplifies many complex problems instantly.
Common Mistakes
- Confusing Euler circuits (visit all edges) with Hamiltonian cycles (visit all vertices).
- Assuming all planar graphs require 4 colors when they might be 2-colorable or 3-colorable.
- Applying Cayley's formula to graphs that are not complete graphs (K_n).
More Revision Notes
Ready to test yourself?
Play topic-wise Graph Theory questions in Aspirant Arcade — gamified MCQ practice.
Download Free