Professor's Distilled Notes on Graph

Theory for GATE Toppers

A Word Before We Begin

Graph Theory is not merely another topic in the GATE syllabus; it is the very language of
connections. Within the Computer Science paper, it forms the essential bridge between the
abstract principles of Discrete Mathematics and the practical, high-stakes domain of
Algorithms.1 For any student aspiring to a top rank, a deep, intuitive mastery of this subject is
non-negotiable.

Over five decades of teaching, a clear pattern has emerged: students who attempt to
memorize formulas and theorems in isolation often falter under pressure. The ones who
consistently achieve top-10 ranks are those who build a robust intuition. They understand not
just what an algorithm does, but why it is designed that way, why it works, and, most critically,
when to apply it over another. These notes are engineered to cultivate that intuition.

Each chapter is a self-contained module focusing on a core concept mandated by the GATE
syllabus. The structure is methodical and designed for maximum retention. First, the
fundamental theory is presented in a distilled form, augmented with shortcuts and mental
models developed over decades in the classroom. Second, this theory is immediately applied
to a challenging, high-caliber GATE problem to demonstrate how these concepts are tested
under exam conditions. Finally, each concept is grounded in a tangible, real-world scenario to
ensure the knowledge is not just learned, but understood and remembered.

Chapter 1: Connectivity - The Fabric of a Graph

Concept 1.1: Graph Basics

A graph, formally denoted as G=(V,E), is a mathematical structure used to model relationships
between objects.4
●​ Vertex (V): A vertex (or node) represents an object, an entity, or a point.
●​ Edge (E): An edge (or link) represents a connection or relationship between a pair of
vertices.
●​ Adjacency and Incidence: Two vertices are adjacent if they are connected by an edge.
An edge is incident with the vertices it connects.4
●​ Degree of a Vertex (deg(v)): The degree of a vertex is the number of edges incident
with it. A self-loop (an edge connecting a vertex to itself) is counted twice, contributing 2
to the degree.4

The Handshaking Lemma: A Fundamental Shortcut

The sum of the degrees of all vertices in a graph is always equal to twice the number of
edges: ∑v∈V​deg(v)=2∣E∣. This simple formula is a powerful tool for verification in MCQ and
numerical answer type questions.4
A direct and invaluable consequence of this lemma is that in any undirected graph, the
number of vertices with an odd degree must be even. This is a 5-second sanity check. If a
problem asks for a graph with certain properties and the construction leads to an odd number
of odd-degree vertices, an error has been made.

A Lexicon of Graph Types

GATE questions frequently test properties of specific graph structures.
●​ Simple Graph: An undirected graph with no self-loops and no more than one edge
between any two vertices.4
●​ Multigraph: A graph that may have multiple edges between the same pair of vertices.
●​ Complete Graph (Kn​): A simple graph with n vertices where every pair of distinct
vertices is connected by an edge. It has 2n(n−1)​edges.4
●​ Bipartite Graph: A graph whose vertex set V can be partitioned into two disjoint sets, U
and W, such that every edge connects a vertex in U to one in W. A graph is bipartite if and
only if it has no odd-length cycles.4
●​ Cycle Graph (Cn​): A graph with n vertices and n edges forming a single cycle.

The Vocabulary of Movement

The distinction between different types of sequences of vertices and edges is critical.
●​ Walk: A sequence of vertices and edges, where vertices and edges can be repeated.
●​ Trail: A walk in which no edge is repeated.
●​ Path: A walk in which no vertex is repeated (and thus no edge is repeated).
●​ Circuit: A closed trail (starts and ends at the same vertex).
●​ Cycle: A closed path of length 3 or more, where only the start and end vertices are the
same.6
Concept 1.2: Advanced Connectivity

Connectivity quantifies the resilience of a graph to the removal of its elements.7

●​ Connected and Disconnected Graphs: A graph is connected if there is a path
between every pair of vertices. If not, it is disconnected and consists of two or more
connected components.7
●​ Cut-Vertex (Articulation Point): A vertex whose removal increases the number of
connected components. These represent critical single points of failure in a network.7
●​ Cut-Edge (Bridge): An edge whose removal increases the number of connected
components. A crucial property is that an edge is a bridge if and only if it does not lie on
any cycle.10
●​ Vertex Connectivity (κ(G)): The minimum number of vertices whose removal
disconnects the graph or reduces it to a single vertex. A graph is k-vertex-connected if
κ(G)≥k.7
●​ Edge Connectivity (λ(G)): The minimum number of edges whose removal disconnects
the graph. A graph is k-edge-connected if λ(G)≥k.7

Whitney's Inequality: Instantaneous Bounds

For any graph G, the following relationship holds: κ(G)≤λ(G)≤δ(G), where δ(G) is the minimum
degree of any vertex in the graph. This inequality provides immediate upper and lower bounds
for connectivity measures, which can be very useful for eliminating options in MCQs.10
Menger's Theorem: The "Lifeline" Principle
The connectivity values κ(G) and λ(G) are not just abstract numbers; Menger's Theorem
provides a profound physical interpretation. For two non-adjacent vertices u and v, the
minimum number of vertices needed to disconnect them (local connectivity, κ(u,v)) is exactly
equal to the maximum number of vertex-disjoint paths between them.13
This theorem is a game-changer because it transforms a "removal" problem into a
"path-finding" problem. Instead of thinking about what to delete to break a connection, one
can think about how many independent "lifelines" exist between two points. This is often a
more intuitive way to reason about a graph's robustness and forms the theoretical foundation
for network flow problems.7

Toughest GATE Problem: Analysis of Bridges

Problem: (GATE CSE 2015, Set 2) "In a connected graph, a bridge is an edge whose removal
disconnects a graph. Which one of the following statements is True?".11

(A) A tree has no bridge.

(B) A bridge cannot be part of a simple cycle.
(C) Every edge of a clique with size ≥3 is a bridge.
(D) A graph with bridges cannot have a cycle.
Solution Breakdown:
This question is challenging because it tests four distinct concepts under the guise of a single
question, requiring a mental library of examples and counterexamples.11
1.​ (A) A tree has no bridge: This is False. A tree is a minimally connected graph; it
contains no cycles. The removal of any edge from a tree will disconnect it. Therefore,
every edge in a tree is a bridge.11
2.​ (B) A bridge cannot be part of a simple cycle: This is True. This statement is
essentially the definition of a bridge from a different perspective. If an edge (u,v) is part
of a cycle, there must be at least two distinct paths between u and v. Removing the edge
(u,v) leaves the other path intact, so the graph remains connected. Thus, no edge in a
cycle can be a bridge.11
3.​ (C) Every edge of a clique with size ≥3 is a bridge: This is False. A clique, or a
complete graph Kn​, is maximally connected. In a Kn​with n≥3, removing any single edge
(u,v) leaves the vertices u and v still connected through any of the other n−2 vertices. The
graph remains strongly connected.11
4.​ (D) A graph with bridges cannot have a cycle: This is False. A simple counterexample
is a "dumbbell" graph, formed by connecting two triangles with a single edge. The two
triangles are cycles, and the connecting edge is a bridge.

This problem reveals a common GATE strategy: testing definitions by exploring their
boundaries and their "negative space"—what they imply something is not.

Real-World Problem: Reliability of a Telecommunication Network

Scenario: Consider the design of a national internet backbone, a network connecting major
data centers across the country. The goal is to create a network that is resilient to failures,
such as a power outage or a targeted cyberattack taking a data center offline.16

Modeling and Application:

●​ Vertices: The data centers or major network switching stations.
●​ Edges: The high-capacity fiber optic links between the stations.
●​ Problem: How many stations can fail before the network becomes partitioned, potentially
 isolating one part of the country from another?

The answer is precisely the vertex connectivity, κ(G), of the network graph.
●​ If κ(G)=1, the network has a single point of failure—a cut-vertex. The failure of this one
critical station would fragment the entire network. Identifying such vulnerabilities is a
primary task for network architects.
●​ To enhance reliability, network designers must add redundant links to increase the
graph's connectivity. A network designed to have κ(G)=3 is far more robust, as it can
withstand the simultaneous failure of any two stations and still maintain nationwide
connectivity. This demonstrates a direct and critical application of graph connectivity in
designing fault-tolerant systems.

Chapter 2: Traversal - Navigating the Labyrinth

Concept 2.1: Breadth-First Search (BFS) vs. Depth-First Search (DFS)

Graph traversal is the process of systematically visiting every vertex in a graph. The two
fundamental strategies are BFS and DFS.18
●​ Breadth-First Search (BFS): This algorithm explores the graph "level by level" from a
given source vertex. It uses a Queue (First-In-First-Out) to manage which vertex to visit
next. Because it explores all neighbors at the current distance before moving to
neighbors farther away, BFS is guaranteed to find the shortest path in an unweighted
graph, where "shortest" means the minimum number of edges.19
●​ Depth-First Search (DFS): This algorithm explores as far as possible along each branch
before backtracking. It uses a Stack (Last-In-First-Out), which is often implemented
implicitly through function recursion. DFS is highly effective for tasks like cycle detection,
finding connected components, and topological sorting.19
●​ Complexity: For a graph represented using an adjacency list, both BFS and DFS have a
time complexity of O(V+E). The space complexity for both is O(V) in the worst case.20

Analogy: Ripples vs. Tunnels

A powerful way to internalize the difference is through a simple analogy.
●​ BFS is like dropping a stone in a pond. The traversal expands from the source in
concentric circles, or ripples. It visits all nodes at distance 1, then all nodes at distance 2,
and so on. This is precisely why it is the natural choice for finding the shortest path in
 terms of edge count.25
●​ DFS is like exploring a cave system. You pick a tunnel and follow it as deep as you can.
When you hit a dead end, you backtrack to the previous junction and try an unexplored
tunnel. This exhaustive, depth-oriented exploration makes it ideal for solving mazes or
determining if a path between two points exists at all.26

Toughest GATE Problem: Analysis of Articulation Points and DFS

Problem: (GATE CSE 2021, Set 1) This is a multi-select question about an articulation point in
a connected undirected graph G and its properties with respect to a DFS tree T obtained from
G.27

The correct statements are:

(B) Root of T is an articulation point in G if and only if it has 2 or more children.
(D) If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of
u in T, then all paths from x to y in G must pass through u.
28 is correct and (D) is false. Let's re-evaluate based on the source)
Solution Breakdown:
This question tests a deep understanding of what the structure of a DFS tree reveals about
the original graph's connectivity. The key is to understand the role of back-edges—edges in G
that are not in T and connect a vertex to one of its ancestors in the DFS tree.
●​ (A) Root of T can never be an articulation point in G: False. A root with two or more
children is an articulation point.
●​ (B) Root of T is an articulation point in G if and only if it has 2 or more children:
True. If the root has only one child, removing it leaves the rest of the graph (the subtree
of that child) connected. If it has two children, say c1​and c2​, there can be no edge in G
directly connecting the subtree of c1​to the subtree of c2​. If such an edge existed, the
DFS traversal would have made one subtree part of the other, resulting in only one child.
Thus, removing the root disconnects these subtrees.28
●​ (C) A leaf of T can be an articulation point in G: False. A leaf in the DFS tree has no
descendants in the tree. All its neighbors in G must have been visited before it, meaning
they are its ancestors. Removing the leaf cannot disconnect any of its neighbors from
each other, as they are all "above" it in the tree and connected through the main tree
structure.28
●​ (D) If u is an articulation point... all paths from an ancestor x to a descendant y
must pass through u: False. This is the most subtle option. A non-root vertex u is an
articulation point if it has a child v such that no back-edge from v's subtree connects to
an ancestor of u. This makes u the sole connection point for that subtree. However,
 another descendant of u, say y (from a different child's subtree), could have a back-edge
to an ancestor of u. This would create a path from ancestor x to descendant y that
bypasses u entirely. Therefore, not all paths must pass through u.28

This question is a masterclass in testing the implications of DFS, where the presence or
absence of back-edges determines the graph's connectivity points.

Real-World Problem: Web Crawling by Search Engines

Scenario: A search engine like Google needs to discover and index the billions of pages on
the World Wide Web. It starts with a list of known, authoritative "seed" URLs and must
systematically explore the web from there.21

Modeling and Application (BFS):

●​ Vertices: Individual web pages (URLs).
●​ Edges: Hyperlinks pointing from one page to another.
●​ Process:
1.​ Initialization: The crawler begins with a queue containing the seed URLs (e.g.,
[Link], [Link]). A visited set is empty.
2.​ Step 1: Dequeue [Link]. Add it to the visited set. Parse the HTML of the page
and extract all unique hyperlinks. For each new, unvisited link found, enqueue it.
3.​ Step 2: Dequeue [Link]. Repeat the process.
4.​ Step 3: Dequeue the first link found on [Link] and continue.
●​ Why BFS is Ideal: The level-by-level "ripple" approach of BFS is perfectly suited for web
crawling. It ensures that pages closer to the authoritative seed URLs are discovered first.
This is important for ranking, as pages linked directly by a major site are often more
relevant than pages buried many clicks deep. BFS also allows the crawl to be easily
constrained (e.g., "crawl up to a depth of 10") to manage the immense scale of the web.21

Table: BFS vs. DFS: A Strategic Comparison

Feature Breadth-First Search (BFS) Depth-First Search (DFS)

Full Name Breadth-First Search Depth-First Search

 Data Structure Queue (FIFO - Stack (LIFO -
First-In-First-Out) Last-In-First-Out) or
Recursion

Traversal Order Level by level; explores all Explores as deep as

neighbors at the present possible down one path
depth before moving to the before backtracking to
next level. explore other paths.

Shortest Path Guarantees finding the Does not guarantee finding

shortest path in an the shortest path.
unweighted graph.

Space Complexity O(w), where w is the O(h), where h is the

maximum width of the maximum depth of the
graph. Can be O(V) in the graph. More
worst case (e.g., a memory-efficient for deep,
complete graph). narrow graphs.

Time Complexity O(V+E) with adjacency list. O(V+E) with adjacency list.

Key Applications Finding shortest path in Cycle detection,

unweighted graphs, web topological sorting, solving
crawling, social network puzzles with backtracking
analysis (finding (e.g., mazes), finding
connections), finding strongly connected
connected components. components.

Infinite Loops Not a concern if a visited Can get trapped in very

set is used. Explores finite long or infinite paths if not
levels. handled with a visited set.

References: 25

Chapter 3: Minimum Spanning Trees - The Optimal

Skeleton
Concept 3.1: The Cut and Cycle Properties

A Minimum Spanning Tree (MST) of a connected, edge-weighted, undirected graph is a

spanning tree (a subgraph that connects all vertices with V−1 edges and no cycles) with the
minimum possible total edge weight.34 The greedy algorithms that find MSTs are proven
correct by two fundamental properties.
●​ Cut Property: Consider any cut (a partition of the vertices into two disjoint sets, S and
V−S). Let e be an edge with the minimum weight among all edges crossing the cut (i.e.,
connecting a vertex in S to one in V−S). The cut property guarantees that this edge e is
part of every MST of the graph. This is the core principle behind Prim's algorithm.34
●​ Cycle Property: For any cycle C in the graph, the edge with the largest weight in that
cycle cannot be part of any MST. Removing this heaviest edge breaks the cycle while
keeping the graph connected, and a spanning tree with a smaller total weight can be
formed. This is the core principle behind Kruskal's algorithm.34
●​ Uniqueness: If all edge weights in the graph are distinct, there will be exactly one unique
MST.34 This is a common and useful assumption in GATE problems.

These two properties can be thought of as the "Greedy Stays" and "Greedy Throws" rules.
The Cut Property provides a safe rule to include an edge (a "Greedy Stay"), as the lightest
edge crossing a cut is a locally optimal choice that is guaranteed to be globally optimal. The
Cycle Property provides a safe rule to exclude an edge (a "Greedy Throw"), as the heaviest
edge in any cycle is always a suboptimal choice.

Concept 3.2: Prim's vs. Kruskal's Algorithm

●​ Prim's Algorithm: This is a vertex-based greedy algorithm. It starts from an arbitrary

vertex and "grows" the MST by adding one vertex at a time. In each step, it finds the
cheapest edge that connects a vertex already in the growing tree to a vertex outside the
tree. This process is efficiently managed using a Priority Queue (Min-Heap). Prim's is
generally preferred for dense graphs (where ∣E∣ is close to ∣V∣2).37
●​ Kruskal's Algorithm: This is an edge-based greedy algorithm. It starts with a forest
where each vertex is its own tree. It considers all edges in increasing order of weight. In
each step, it adds the next cheapest edge to the MST, provided that adding the edge
does not form a cycle. To efficiently detect cycles, it uses a Union-Find data structure.
 Kruskal's is generally preferred for sparse graphs (where ∣E∣ is close to ∣V∣).37

A helpful analogy is to visualize Prim's as growing a single blob outwards from a starting
point, always consuming the nearest vertex. In contrast, Kruskal's starts with many separate
islands (vertices) and uses the cheapest available bridges (edges) to connect them until a
single landmass is formed.

Toughest GATE Problem: Analysis of MST Properties

Problem: (GATE CSE 2022, Question 39) For a simple undirected weighted graph with distinct
positive edge weights, which of the following statements are TRUE? 39

(A) The edge with the second smallest weight is always part of any MST.
(B) One or both of the edges with the third and fourth smallest weights are part of any MST.
(C) For any cut, the minimum weight edge crossing the cut is always part of any MST.
(D) The graph can have multiple MSTs.
Solution Breakdown:
This question tests the theoretical underpinnings of MST algorithms, not just their execution.
Since edge weights are distinct, the MST is unique.
1.​ (A) True: Kruskal's algorithm sorts edges by weight. It will always select the edge with
the smallest weight. It will then select the second-smallest weight edge. Since two edges
cannot form a cycle, this edge is guaranteed to be in the unique MST.
2.​ (B) True: After selecting the two smallest edges, Kruskal's considers the third-smallest. If
adding it creates a cycle with the first two, it is discarded, and the algorithm moves to the
fourth-smallest edge. If it does not create a cycle, it is included. In either scenario, the
logic of building a connected acyclic graph ensures one of these edges will be
considered and likely included to connect components.
3.​ (C) True: This is a direct statement of the Cut Property, a fundamental theorem for
MSTs.
4.​ (D) False: As stated, a graph with distinct edge weights has a unique MST.

This problem demonstrates that a deep understanding of the principles behind Kruskal's
algorithm and the Cut Property is more efficient than attempting to construct a graph and
simulate the process.

Real-World Problem: Designing a Cost-Effective Electrical Grid

Scenario: An energy company needs to build a power grid to connect several towns,
substations, and a new power plant in a rural region. The goal is to ensure every location is
connected to the grid while minimizing the total cost of laying high-voltage power lines.35

Modeling and Application:

●​ Vertices: The towns, substations, and the power plant.
●​ Edges: The potential routes where power lines can be laid.
●​ Weights: The cost associated with each route, which depends on factors like distance,
terrain difficulty, and land acquisition rights.
●​ Solution: The problem is to find a network of power lines that connects all locations with
the minimum possible total construction cost. This is a classic application of a Minimum
Spanning Tree. By modeling the locations and routes as a weighted graph, engineers can
use Prim's or Kruskal's algorithm to find the MST. The resulting set of edges in the MST
represents the most cost-effective layout for the electrical grid, guaranteeing full
connectivity at the lowest capital expenditure.

Table: Prim's vs. Kruskal's: Choosing Your MST Algorithm

Feature Prim's Algorithm Kruskal's Algorithm

Approach Vertex-based: Grows a Edge-based: Sorts all

single connected tree from edges and adds the
a starting vertex. cheapest ones that don't
form a cycle, merging a
forest of trees.

Data Structure Priority Queue (Min-Heap) Union-Find (for cycle

detection) and a sorted list
of edges.

Time Complexity O(V2) (adjacency matrix) or O(ElogE) or O(ElogV)

O(ElogV) (binary heap). (dominated by edge
sorting).

Best For Dense graphs, where E is Sparse graphs, where E is

close to V. Also when
 close to V2. edges are already sorted.

Cycle Handling Implicitly avoids cycles by Explicitly checks for cycles

only adding edges to using the Union-Find data
vertices not yet in the tree. structure before adding an
edge.

Intermediate State Always maintains a single Maintains a forest of

connected tree. disconnected trees until
the final step.

References: 38

Chapter 4: Shortest Paths - The Efficient Route

Concept 4.1: Single-Source Shortest Paths (SSSP)

The SSSP problem aims to find the shortest path from a designated source vertex to all other
vertices in a weighted graph.
●​ Dijkstra's Algorithm: This is a greedy algorithm that solves the SSSP problem for graphs
with non-negative edge weights.45 It maintains a set of vertices whose shortest path
from the source is finalized. In each step, it greedily selects the unvisited vertex with the
smallest known distance from the source, finalizes it, and updates the distances of its
neighbors. A priority queue is used to make this selection efficient.46
●​ Bellman-Ford Algorithm: This algorithm is more versatile as it solves the SSSP problem
even when the graph has negative edge weights.47 It works by systematically "relaxing"
every edge in the graph for​
∣V∣−1 iterations. A final, ∣V∣-th iteration is used to detect if a negative-weight cycle
exists (if any distance can still be improved, a negative cycle is reachable from the
source).48 Its time complexity,​
O(V⋅E), is higher than Dijkstra's.

A helpful way to remember their key difference is to personify them. Dijkstra's algorithm is fast
and optimistic; its greedy approach assumes that once a path's cost is finalized, a shorter one
will never be found. This optimism is its downfall with negative edges, hence the rule: "No
Negative Greed." Bellman-Ford is slower and more "paranoid." It re-evaluates every possible
path improvement across all edges ∣V∣−1 times, never trusting a path is optimal until the very
end. This exhaustive checking allows it to handle negative weights and detect negative
cycles.47

Toughest GATE Problem: Dijkstra's with a Negative Edge

Problem: (GATE CSE 2008, Question 45) Run Dijkstra's algorithm on a given graph that
contains a negative weight edge and determine to which vertices it computes the correct
shortest path distances.50

Solution Breakdown:
In the specific graph provided in the question, Dijkstra's algorithm, when run from the source
vertex 'a', correctly computes the shortest path to all other vertices. This is a trap question for
those who only memorize the rule "Dijkstra fails with negative edges."
The deeper truth is that Dijkstra's may fail. The failure occurs if the algorithm's greedy choice
finalizes a path to a vertex u as optimal, when a different, currently longer path exists that will
later encounter a negative edge and ultimately become a shorter path to u. In the graph from
this 2008 question, the order in which vertices are extracted from the priority queue is such
that the negative edge is processed and its path-shortening effect is accounted for before
any incorrect path is finalized. The greedy choices happen to be the correct choices
throughout the execution.50 This question tests true understanding over rote memorization.

Concept 4.2: All-Pairs Shortest Paths (APSP)

The APSP problem is to find the shortest path between every pair of vertices in a graph.
●​ Floyd-Warshall Algorithm: This is a dynamic programming algorithm that solves the
APSP problem. It can handle positive and negative edge weights but not negative-weight
cycles.51 The algorithm works by iteratively considering every vertex​
k as a potential intermediate vertex in the shortest path between any two other vertices, i
and j.
●​ Core Recurrence: The fundamental operation is dist[i][j] = min(dist[i][j], dist[i][k] +
dist[k][j]).
●​ Complexity: Its structure of three nested loops gives it a straightforward time complexity
 of O(V3).51

The three nested loops (for k, for i, for j) can be understood intuitively. The outer k loop grants
"permission" for paths to transit through certain vertices. When k=1, the algorithm finds all
shortest paths that are allowed to pass through vertex 1. When k=2, it finds all shortest paths
allowed to pass through vertices from the set {1, 2}. By the time the k loop finishes, paths have
been given permission to transit through any intermediate vertex, thus yielding the true
all-pairs shortest paths. This perspective clarifies the dynamic programming nature of the
algorithm, where the solution for k intermediate vertices is built upon the solution for k-1
vertices.53

Toughest GATE Problem: The Paradigm of Floyd-Warshall

Problem: (GATE CSE 2016, Set 2) "The Floyd-Warshall algorithm for all-pair shortest paths
computation is based on..." The options are Greedy, Divide-and-Conquer, Dynamic
Programming, or none.54

Solution Breakdown:
The correct answer is Dynamic Programming. The algorithm exhibits the two hallmark
properties of DP:
1.​ Optimal Substructure: The shortest path from i to j that is allowed to use intermediate
vertices from {1,..., k} is either (a) the shortest path using only vertices from {1,..., k-1}, or
(b) the concatenation of the shortest path from i to k and the shortest path from k to j
(both using only {1,..., k-1} as intermediates). The algorithm chooses the minimum of
these two cases.53
2.​ Overlapping Subproblems: The calculation of shortest paths for a given k repeatedly
uses the results computed for k-1.

This question underscores that GATE expects an understanding of the design paradigm
behind an algorithm, not merely its implementation details.

Real-World Applications

●​ Dijkstra's in Route Planning: Navigation systems like Google Maps model the road
network as a massive graph where intersections are vertices and road segments are
edges with weights representing travel time. When a user requests directions, a
Dijkstra-like algorithm finds the fastest route from the source to the destination. Since
 travel times are non-negative, Dijkstra's is an excellent choice.55
●​ Bellman-Ford in Network Routing: Distance-vector routing protocols, like the Routing
Information Protocol (RIP), are essentially distributed implementations of the
Bellman-Ford algorithm. Each router maintains a table of shortest distances to other
routers and periodically shares this table with its neighbors. Neighbors use this
information to update their own tables via the relaxation step. This allows the network to
collectively compute shortest paths for data packets.47

Table: Shortest Path Algorithm Selector

Feature Dijkstra's Algorithm Bellman-Ford Floyd-Warshall

Algorithm Algorithm

Problem Type Single-Source Single-Source All-Pairs (APSP)

(SSSP) (SSSP)

Negative Edges Not Allowed Allowed Allowed

Negative Cycles Fails (may give Detects them (and Detects them
incorrect output or reports no solution) (diagonal of
loop) distance matrix
becomes negative)

Time Complexity O(ElogV) (with O(V⋅E) O(V3)

priority queue)

Professor's Tip Default choice for Use for SSSP only if Use only when
SSSP due to speed. negative edges are shortest paths
present. between all pairs
are required.

References: 49

Chapter 5: Matching - Finding the Perfect Pair

Concept 5.1: Bipartite Matching

●​ Definitions:
○​ Bipartite Graph: A graph whose vertices can be divided into two disjoint sets, U and
V, such that every edge connects a vertex in U to one in V.4
○​ Matching: A subset of edges in which no two edges share a common vertex.61
○​ Maximum Matching: A matching that contains the largest possible number of
edges.
○​ Perfect Matching: A matching that covers every vertex in the graph. This is only
possible if ∣U∣=∣V∣.
●​ Augmenting Paths: An augmenting path is a path in the graph that alternates between
edges not in the current matching and edges that are in the matching, starting and
ending at unmatched vertices. Finding such a path and "flipping" its edges (adding the
unmatched edges to the matching and removing the matched ones) increases the size of
the matching by exactly one. This is the core principle behind many matching
algorithms.61

The Max-Flow Min-Cut Shortcut

A powerful technique for solving the maximum bipartite matching problem is to convert it into
a maximum flow problem.63 This unifies two major graph theory topics.
1.​ Transformation: Given a bipartite graph G=(U∪V,E):
○​ Create a new directed graph. Add a source vertex s and a sink vertex t.
○​ Add a directed edge of capacity 1 from s to every vertex in U.
○​ Add a directed edge of capacity 1 from every vertex in V to t.
○​ For every original edge (u,v) with u∈U and v∈V, add a directed edge from u to v with
capacity 1.
2.​ Solution: The value of the maximum flow from s to t in this new network is exactly equal
to the size of the maximum matching in the original bipartite graph. For GATE, being able
to re-frame a matching problem this way provides a potent alternative line of attack.

Toughest GATE Problem: Maximum Edges in a Bipartite Graph

Problem: (GATE CSE 2014, Set 2) "The maximum number of edges in a bipartite graph on 12
vertices is ________.".65
Solution Breakdown:
This question tests the fundamental structure of bipartite graphs. The maximum number of
edges is achieved when the graph is a complete bipartite graph (Km,n​), and the two vertex
partitions are as close in size as possible.
●​ Let the two partitions have sizes m and n. We have m+n=12.
●​ The number of edges in a complete bipartite graph is m×n.
●​ To maximize the product m×n subject to a fixed sum m+n=12, the values of m and n must
be as close as possible. For a sum of 12, this occurs when m=6 and n=6.
●​ Therefore, the maximum number of edges is 6×6=36.

The general formula for the maximum number of edges in a bipartite graph with N vertices is
⌊N2/4⌋. For N=12, this is ⌊144/4⌋=36. Knowing this formula is the ultimate shortcut.

Real-World Problem: Candidate-to-Job Matching

Scenario: A large recruitment agency needs to match a pool of job applicants to a set of
available job positions. The agency wants to maximize the total number of successful
placements.63

Modeling and Application:

●​ Bipartite Graph Model:
○​ One set of vertices, U, represents the job applicants.
○​ The second set of vertices, V, represents the available job positions.
○​ An edge exists between an applicant u∈U and a job v∈V if and only if applicant u is
qualified for and interested in job v.
●​ Goal: The agency's objective is to find the maximum number of pairs (u,v) such that each
applicant is assigned to at most one job, and each job is filled by at most one applicant.
●​ Solution: This is precisely the maximum bipartite matching problem. The size of the
maximum matching gives the maximum number of placements that can be made.
Algorithms like the Hopcroft-Karp algorithm or the max-flow reduction are used in the
backend of job portals and recruitment software to solve this problem efficiently.

Chapter 6: Coloring - The Art of Separation

Concept 6.1: Vertex Coloring and the Chromatic Number (χ(G))

●​ Definitions:
○​ Proper Vertex Coloring: An assignment of colors to the vertices of a graph such
that no two adjacent vertices share the same color.67
○​ Chromatic Number (χ(G)): The minimum number of colors required for a proper
vertex coloring of graph G.67
●​ Properties for Standard Graphs: Knowing these values is essential for GATE.
○​ χ(Kn​)=n. A complete graph on n vertices requires n distinct colors.
○​ χ(Cn​)=2 if n is even, and χ(Cn​)=3 if n is odd.
○​ A graph is 2-colorable if and only if it is bipartite (and has at least one edge).
○​ For any tree with at least one edge, χ(Tree)=2.67

Bounding the Chromatic Number

Finding the exact chromatic number is an NP-hard problem. Therefore, GATE questions will
always have a structural trick or rely on properties that simplify the problem. The most
effective strategy is to bound the chromatic number.
●​ Lower Bound: The size of the largest clique (a complete subgraph) in G, denoted ω(G),
is a lower bound: χ(G)≥ω(G). A graph containing a triangle (K3​) will require at least 3
colors.
●​ Upper Bound: A simple upper bound is χ(G)≤Δ(G)+1, where Δ(G) is the maximum vertex
degree in the graph. Brooks' Theorem provides a tighter bound: for any connected
graph that is not a complete graph or an odd cycle, χ(G)≤Δ(G).67

When faced with a coloring problem, the first step should be to find the largest clique (ω(G))
and the maximum degree (Δ(G)). This immediately establishes a range $$ where the
chromatic number must lie, often narrowing the possibilities to the correct answer.

Toughest GATE Problem: Analysis of Chromatic Number Properties

Problem: (GATE CSE 2024, Set 1) For a graph G with n vertices and chromatic number k,
which of the following statements are always TRUE? 69

(A) G contains a complete subgraph with k vertices.

(B) G contains an independent set of size at least ⌈n/k⌉.
(C) G contains at least k(k−1)/2 edges.
(D) G contains a vertex of degree at least k.
Solution Breakdown:
This is a purely theoretical question testing the fundamental implications of the chromatic
number definition.
1.​ (A) False: A classic counterexample is the 5-cycle, C5​. Its chromatic number is k=3, but it
does not contain a K3​(a triangle) as a subgraph.
2.​ (B) True: A proper k-coloring partitions the n vertices into k independent sets (the color
classes). Let the sizes of these sets be s1​,s2​,...,sk​. We have ∑si​=n. By the pigeonhole
principle, at least one of these sets must have a size of at least the average, which is n/k.
3.​ (C) True: For the chromatic number to be exactly k, every color class must be connected
to every other color class by at least one edge. If any two color classes, say Ci​and Cj​,
were not connected, they could be merged and assigned the same color, reducing the
required colors to k−1, which contradicts that χ(G)=k. There are (2k​)=2k(k−1)​pairs of
color classes, so there must be at least that many edges.
4.​ (D) False: A classic counterexample is the complete graph Kk​. Its chromatic number is k,
but every vertex has a degree of exactly k−1.

Real-World Problem: University Exam Timetabling

Scenario: A university needs to schedule final exams for all its courses. The primary
constraint is that no student can have two exams scheduled in the same time slot.68

Modeling and Application:

●​ Vertices: Each unique course offered by the university (e.g., CS101, MA201).
●​ Edges: An edge connects two vertices (courses) if at least one student is enrolled in
both. This edge represents a scheduling conflict.
●​ Colors: The available exam time slots (e.g., Monday 9 AM, Monday 2 PM, etc.).
●​ Goal: Assign a time slot (color) to each exam (vertex) such that no two conflicting exams
are scheduled at the same time, using the minimum possible number of time slots.

This is a direct application of the graph coloring problem. A proper vertex coloring of this
"conflict graph" corresponds to a valid, conflict-free exam schedule. The chromatic number,
χ(G), of this graph represents the absolute minimum number of time slots required to
schedule all exams. University administration software uses heuristics and algorithms based
on graph coloring to solve this complex logistical problem each semester.

Conclusion: Final Theorems and Parting Advice

The journey through graph theory reveals a set of powerful, interconnected ideas. The key to
success in GATE is not to see these as isolated topics but as a unified toolkit for analyzing
networks and relationships. The core mental models presented here are designed to be the
shortcuts that bridge theory and application:
●​ Degree Sum Parity: A quick check for graph validity.
●​ Menger's Lifeline Principle: Translating connectivity from a removal problem to a
path-finding problem.
●​ Ripples (BFS) vs. Tunnels (DFS): An intuitive guide to choosing the right traversal
algorithm.
●​ Greedy Stays (Cut) vs. Greedy Throws (Cycle): The two faces of MST correctness.
●​ Growing a Blob (Prim's) vs. Connecting Islands (Kruskal's): A visual heuristic for
selecting an MST algorithm.
●​ No Negative Greed (Dijkstra's) vs. The Paranoid Algorithm (Bellman-Ford): A
personification to remember shortest-path algorithm constraints.
●​ Permission to Transit (Floyd-Warshall): An intuitive grasp of the dynamic programming
approach in APSP.
●​ Max-Flow for Matching: A powerful reduction that unifies two major problem domains.
●​ Bounding the Chromatic Number: The practical first step to solving any coloring
problem by narrowing the search space.

Graph theory questions in GATE are fundamentally tests of pattern recognition. A graph that
appears complex on the surface is almost always a standard structure in disguise (e.g.,
bipartite, a cycle with chords) or possesses a key property that makes a specific algorithm's
application straightforward. The primary task is not merely to compute a solution but to first
identify the underlying structure. Cultivating this skill of rapid identification and applying the
appropriate mental model is the definitive path to a top rank.

Works cited

1.​ CS Computer Science and Information Technology - GATE 2024, accessed

August 18, 2025, [Link]
2.​ GATE CSE 2025 Syllabus, accessed August 18, 2025,
[Link]
3.​ GATE CSE Syllabus 2025 OUT; Check Marks Weightage, Important Topics and
Download Official PDF - Jagran Josh, accessed August 18, 2025,
[Link]
ownload-1690889440-1
4.​ Mathematics | Graph Theory Basics - Set 2 - GeeksforGeeks, accessed August
18, 2025,
[Link]
eory-basics/
5.​ A Gentle Introduction To Graph Theory | by Vaidehi Joshi | basecs - Medium,
accessed August 18, 2025,
[Link]
 d8
6.​ GATE CS Notes - GeeksforGeeks, accessed August 18, 2025,
[Link]
7.​ Connectivity (graph theory) - Wikipedia, accessed August 18, 2025,
[Link]
8.​ Graph Theory - Connectivity - Tutorialspoint, accessed August 18, 2025,
[Link]
9.​ Section 4.1 Connectivity: Properties and Structure - UPCommons, accessed
August 18, 2025,
[Link]
ce=1&isAllowed=y
10.​Connectivity - Graph Theory - Kent, accessed August 18, 2025,
[Link]
htm
11.​ Graph Theory: GATE CSE 2015 Set 2 | Question: 50 - GATE Overflow, accessed
August 18, 2025, [Link]
12.​Vertex and edge connectivity | Graph Theory Class Notes - Fiveable, accessed
August 18, 2025,
[Link]
uide/ezJrk6muPyRLcoOL
13.​Menger's theorem - Wikipedia, accessed August 18, 2025,
[Link]
14.​Menger's Theorem: A Comprehensive Guide, accessed August 18, 2025,
[Link]
mal-graph-theory
15.​[Link] Year GATE Questions (With Solutions) | PDF | Vertex (Graph Theory) -
Scribd, accessed August 18, 2025,
[Link]
s-with-solutions
16.​[Link], accessed August 18, 2025,
[Link]
s#:~:text=Examples%20of%20Vertex%20Connectivity%20in%20Real%2DWorld%
20Networks,-Vertex%20connectivity%20has&text=Communication%20Networks
%3A%20Vertex%20connectivity%20is,be%20transmitted%20reliably%20betwee
n%20nodes.
17.​Vertex Connectivity: The Key to Reliable Networks - Number Analytics, accessed
August 18, 2025,
[Link]
s
18.​GATE Questions on Graph Traversal - Naukri Code 360, accessed August 18,
2025,
[Link]
19.​Graph-Based Algorithms for GATE Exam [2024] - GeeksforGeeks, accessed
August 18, 2025,
[Link]
20.​Graph Data Structure Notes for GATE Exam [2024] - GeeksforGeeks, accessed
August 18, 2025,
[Link]
21.​Applications, Advantages and Disadvantages of Breadth First ..., accessed August
18, 2025,
[Link]
22.​19.3. Graph Traversals — OpenDSA Data Structures and Algorithms Modules
Collection, accessed August 18, 2025,
[Link]
ml
23.​What are some examples of real world application of a depth first search? -
Quora, accessed August 18, 2025,
[Link]
a-depth-first-search
24.​Time and Space Complexity of DFS and BFS Algorithm - GeeksforGeeks,
accessed August 18, 2025,
[Link]
algorithm/
25.​8.4 Comparison of BFS and DFS - Intro To Algorithms - Fiveable, accessed August
18, 2025,
[Link]
dy-guide/XtTDnwoQG6pzUB9Y
26.​When to Use Depth First Search vs Breadth First Search - Hypermode, accessed
August 18, 2025,
[Link]
27.​Algo -4 - Depth First Search DFS - GATE PYQs Complete Analysis | Graph
Traversals | Sachin Mittal - YouTube, accessed August 18, 2025,
[Link]
28.​Data Structures: GATE CSE 2021 Set 1 | Question: 41 - GATE Overflow, accessed
August 18, 2025, [Link]
29.​Breadth-First Search (BFS) - CelerData, accessed August 18, 2025,
[Link]
30.​Breadth-First Search (BFS) Algorithm | by Anish - Medium, accessed August 18,
2025,
[Link]
74d
31.​Difference between BFS and DFS - GeeksforGeeks, accessed August 18, 2025,
[Link]
32.​Difference Between BFS and DFS - Scaler Blog, accessed August 18, 2025,
[Link]
33.​DFS vs BFS Algorithm (All Differences With Example) - WsCube Tech, accessed
August 18, 2025, [Link]
34.​Properties of Minimum Spanning Tree (MST) - GeeksforGeeks, accessed August
18, 2025,
[Link]
35.​Minimum spanning tree - Wikipedia, accessed August 18, 2025,
[Link]
36.​[Solved] Let G be any connected, weighted, undirected graph. I. G ha - Testbook,
accessed August 18, 2025,
[Link]
cted-graph--5dd94492f60d5d2b07a5c660
37.​4.3 Minimum Spanning Trees - Algorithms, 4th Edition, accessed August 18, 2025,
[Link]
38.​Difference between Prim's and Kruskal's algorithm for MST ..., accessed August
18, 2025,
[Link]
orithm-for-mst/
39.​Algorithms: GATE CSE 2022 | Question: 39 - GATE Overflow, accessed August 18,
2025, [Link]
40.​Applications of the 20 Most Popular Graph Algorithms - Memgraph, accessed
August 18, 2025, [Link]
41.​Difference between Prims and Kruskal Algorithm - BYJU'S, accessed August 18,
2025, [Link]
42.​When should I use Kruskal as opposed to Prim (and vice versa)? - Stack Overflow,
accessed August 18, 2025,
[Link]
osed-to-prim-and-vice-versa
43.​Kruskal's vs Prim's Algorithm: The Ultimate Showdown - HeyCoach, accessed
August 18, 2025, [Link]
44.​Prims and Kruskal Algorithm - Scaler Blog, accessed August 18, 2025,
[Link]
45.​Dijkstra's algorithm - Wikipedia, accessed August 18, 2025,
[Link]
46.​Dijkstra's Algorithm to find Shortest Paths from a Source to all ..., accessed
August 18, 2025,
[Link]
go-7/
47.​Bellman–Ford algorithm - Wikipedia, accessed August 18, 2025,
[Link]
48.​Bellman–Ford Algorithm - GeeksforGeeks, accessed August 18, 2025,
[Link]
49.​difference between Bellman Ford and Dijkstra's algorithm - Stack Overflow,
accessed August 18, 2025,
[Link]
-and-dijkstras-algorithm
50.​Algorithms: GATE CSE 2008 | Question: 45 - GATE Overflow, accessed August 18,
2025, [Link]
51.​Floyd–Warshall algorithm - Wikipedia, accessed August 18, 2025,
[Link]
52.​Floyd Warshall Algorithm - GeeksforGeeks, accessed August 18, 2025,
 [Link]
53.​The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
- Testbook, accessed August 18, 2025,
[Link]
shortest--5e020f7db254810d08909d9c
54.​Algorithms: GATE CSE 2016 Set 2 | Question: 14 - GATE Overflow, accessed
August 18, 2025, [Link]
55.​Dijkstra's Algorithm Explained: Comprehensive Guide to Shortest ..., accessed
August 18, 2025,
[Link]
56.​How Is Dijkstra's Algorithm Used In The Real World? | Analytics Steps, accessed
August 18, 2025,
[Link]
57.​Bellman-Ford Algorithm In Real-world Applications - HeyCoach, accessed August
18, 2025,
[Link]
58.​Distance Vector Routing (DVR) Protocol - GeeksforGeeks, accessed August 18,
2025,
[Link]
-protocol/
59.​Shortest Path Algorithm Tutorial with Problems - GeeksforGeeks, accessed
August 18, 2025,
[Link]
60.​1 Bipartite maximum matching - CS@Cornell, accessed August 18, 2025,
[Link]
61.​Matching (Graph Theory) - GeeksforGeeks, accessed August 18, 2025,
[Link]
y/
62.​Matching (graph theory) - Wikipedia, accessed August 18, 2025,
[Link]
63.​Bipartite Matching - University of Notre Dame, accessed August 18, 2025,
[Link]
nelPaperFinal/[Link]
64.​Maximum Bipartite Matching - GeeksforGeeks, accessed August 18, 2025,
[Link]
65.​Graph Theory: GATE CSE 2014 Set 2 | Question: 3 - GATE Overflow, accessed
August 18, 2025, [Link]
66.​Real life Applications of Bipartite Graph - GeeksforGeeks, accessed August 18,
2025,
[Link]
67.​Chromatic Number of a Graph | Graph Colouring - GeeksforGeeks, accessed
August 18, 2025,
[Link]
ing/
68.​Planar Graphs and Graph Coloring - GeeksforGeeks, accessed August 18, 2025,
 [Link]
raphs-graph-coloring/
69.​Graph Theory: GATE CSE 2024 | Set 1 | Question: 41 - GATE Overflow, accessed
August 18, 2025, [Link]
70.​Graph Theory: GATE CSE 2024 | Set 1 | Question: 41, accessed August 18, 2025,
[Link]