Graph Theory

Overview

In the domain of Engineering Mathematics, few structures are as versatile and fundamental as the graph. A graph, in its essence, is an abstract representation of a set of objects where some pairs of the objects are connected by links. We formalise this structure as a set of vertices and a set of edges, denoted by $G = (V, E)$. The applications of this simple yet powerful abstraction are ubiquitous throughout computer science, from modelling computer networks and social connections to representing state transitions in algorithms and dependencies in databases. A firm grasp of graph theory is therefore indispensable for a computer science engineer.

This chapter is designed to provide a rigorous foundation in the principles of graph theory most pertinent to the GATE examination. We begin by establishing the core terminology and formalisms, including various types of graphs and their standard representations, such as adjacency matrices and lists. We then proceed to the critical concept of connectivity, exploring paths, cycles, and components, which are essential for analysing network flow and algorithm traversal. Finally, we shall elucidate more advanced topics, namely matching and colouring, which model solutions to significant optimisation problems in resource allocation, scheduling, and register allocation. A systematic study of these topics will equip the student with the analytical reasoning and problem-solving skills necessary to excel in this section of the examination.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Graph Fundamentals | Defining graphs, their types, and representations. |
| 2 | Connectivity | Analysing paths, cycles, and connected components. |
| 3 | Matching and Colouring | Exploring bipartite matching and graph colouring problems. |

---

Learning Objectives

After completing this chapter, you will be able to:

Define fundamental graph-theoretic terminology and represent graphs using adjacency matrices and lists.

Analyse the connectivity of a graph by identifying paths, cycles, and connected components.

Determine the existence and size of maximum matchings in bipartite graphs.

Apply graph colouring principles to determine the chromatic number of a graph and solve related problems.

---

We now turn our attention to Graph Fundamentals...

Part 1: Graph Fundamentals

Key Definitions

For a simple graph with $n$ vertices $\{v_1, \dots, v_n\}$, the adjacency matrix $\mathbf{A}$ is an $n \times n$ matrix where:

For an undirected graph, $\mathbf{A}$ is symmetric ($\mathbf{A} = \mathbf{A}^T$).

---

Essential Formulas

---

Must Remember

Adjacency Matrix Powers: The entry $(\mathbf{A}^k)_{ij}$ is fundamental. It counts the number of walks of length $k$ from $v_i$ to $v_j$.

* The diagonal entry $(\mathbf{A}^2)_{ii}$ counts walks of length 2 from $v_i$ to itself. This is equivalent to going to a neighbor and returning, so $(\mathbf{A}^2)_{ii} = \deg(v_i)$.
* A graph is connected if and only if for every pair of distinct vertices $(v_i, v_j)$, there is some $k>0$ such that $(\mathbf{A}^k)_{ij} > 0$.

Properties of Trees: For a graph with $n$ vertices, any two of the following properties imply the third, defining a tree:

* The graph is connected.
* The graph is acyclic.
* The graph has exactly $n-1$ edges.

Planarity Condition: For a simple, connected planar graph with $v \ge 3$:

* A necessary condition is $e \le 3v-6$.
* If the graph has no triangles ($C_3$), the condition is stricter: $e \le 2v-4$.
* These are useful for quickly proving a graph is non-planar if the conditions are violated (e.g., $K_5$ and $K_{3,3}$).

Special Graphs:

* Complete Graph ($K_n$): $n$ vertices, $\binom{n}{2}$ edges. Chromatic number $\chi(K_n)=n$.
* Cycle Graph ($C_n$): $n$ vertices, $n$ edges. $\chi(C_n) = 2$ if $n$ is even; $\chi(C_n) = 3$ if $n$ is odd.
* Bipartite Graph: Can be 2-colored. A graph is bipartite if and only if it has no odd-length cycles.

---

Common Mistakes

❌ Connectivity: A graph where every vertex has a degree of at least 1 must be connected.
✅ Correct: This is false. Consider a graph consisting of two disjoint triangles. Every vertex has degree 2, but the graph is not connected.

❌ Counting 3-Cycles: The number of triangles is $\operatorname{trace}(\mathbf{A}^3)$.
✅ Correct: The number of triangles is $\frac{1}{6}\operatorname{trace}(\mathbf{A}^3)$. The trace counts each triangle 6 times (3 starting vertices $\times$ 2 directions).

❌ Euler's Formula: Using $v-e+f=2$ for a disconnected graph.
✅ Correct: For a graph with $k$ connected components, the formula is $v-e+f = 1+k$.

---

Quick Practice

type="MCQ" question="Let $\mathbf{A}$ be the adjacency matrix of a simple graph $G$. If the diagonal entries of $\mathbf{A}^2$ are $(2, 3, 3, 2, 4)$, what is the number of edges in $G$?" options=["5", "7", "14", "28"] answer="7" hint="Use the Handshaking Lemma and the relationship between $\mathbf{A}^2$ and vertex degrees." solution="The diagonal entries of $\mathbf{A}^2$ represent the degrees of the vertices. So, the degrees are 2, 3, 3, 2, and 4. By the Handshaking Lemma, $2|E| = \sum \deg(v) = 2+3+3+2+4 = 14$. Therefore, $|E| = 7$.
Answer: \boxed{7}"

type="NAT" question="A simple connected planar graph has 12 vertices, and each of its faces is bounded by exactly 3 edges. Find the number of edges in the graph." answer="30" hint="Relate the number of faces and edges using the fact that each face is a triangle. Then apply Euler's formula." solution="Let $e$ be the number of edges and $f$ be the number of faces. Since each face is bounded by 3 edges and each edge is shared by exactly 2 faces, we have $3f = 2e$, or $f = \frac{2e}{3}$. By Euler's formula for connected planar graphs, $v - e + f = 2$. Substituting $v=12$ and $f=\frac{2e}{3}$, we get $12 - e + \frac{2e}{3} = 2$. This simplifies to $10 = e - \frac{2e}{3} = \frac{e}{3}$. Thus, $e=30$.
Answer: \boxed{30}"

---

Remember

> The adjacency matrix and its powers reveal deep structural properties of a graph, including connectivity, path counts, and cycle structures.

See full notes for detailed explanations!

---

---

Part 2: Connectivity

Key Definitions

---

Essential Formulas

---

Must Remember

Condition for Connectivity: A simple graph with $n$ vertices and more than $\frac{(n-1)(n-2)}{2}$ edges is guaranteed to be connected. This is a critical threshold.

Condition for Disconnectedness: A simple graph with $n$ vertices and fewer than $n-1$ edges is guaranteed to be disconnected.

Maximizing Edges in a Disconnected Graph: To achieve the maximum number of edges in a disconnected graph with $n$ vertices, partition the vertices into two sets of size $n-1$ and $1$. The component with $n-1$ vertices is made a complete graph ($K_{n-1}$), and the remaining vertex is isolated.

* Number of edges = Edges in $K_{n-1}$ + Edges for isolated vertex = $\frac{(n-1)(n-2)}{2} + 0$.

---

Common Mistakes

❌ Error: Thinking a disconnected graph must be sparse (have very few edges).
✅ Correct: A disconnected graph can be very dense. For example, a graph with 10 vertices can have up to $\frac{(10-1)(10-2)}{2} = \frac{9 \times 8}{2} = 36$ edges and still be disconnected. This is just one edge less than a $K_9$.
---
❌ Error: Mixing up minimum and maximum bounds.
✅ Correct:
* Min edges for a connected graph: $n-1$.
* Max edges for a disconnected graph: $\frac{(n-1)(n-2)}{2}$.

---

Quick Practice

type="NAT" question="What is the maximum number of cut vertices a simple connected graph with 9 vertices can have?" answer="7" hint="Consider a path graph." solution="A path graph $P_n$ has $n-2$ cut vertices (all vertices except the two endpoints). A cycle graph $C_n$ has 0 cut vertices. A complete graph $K_n$ ($n>2$) has 0 cut vertices. To maximize cut vertices, we need a structure like a path. A path graph $P_9$ has $9-2=7$ cut vertices. This is the maximum possible.
Answer: \boxed{7}"

type="MCQ" question="A simple graph $G$ has 15 vertices. Which of the following conditions guarantees that $G$ is connected?" options=["A) $G$ has 14 edges.", "B) $G$ has 90 edges.", "C) $G$ has 92 edges.", "D) Every vertex in $G$ has a degree of at least 2."] answer="C" hint="Recall the maximum number of edges a disconnected graph can have." solution="Let $n=15$ be the number of vertices.
A) $G$ has 14 edges. This is the minimum number of edges for a connected graph (a tree). However, a graph with 14 edges can be disconnected (e.g., a $K_{14}$ with one edge removed, and an isolated vertex). So, this does not guarantee connectivity.
B) $G$ has 90 edges. The maximum number of edges a disconnected graph with $n$ vertices can have is $\frac{(n-1)(n-2)}{2}$. For $n=15$, this is $\frac{(15-1)(15-2)}{2} = \frac{14 \times 13}{2} = 91$. A graph with 90 edges could still be disconnected (e.g., a $K_{14}$ with one edge missing, and an isolated vertex).
C) $G$ has 92 edges. Since the maximum number of edges for a disconnected graph with 15 vertices is 91, any graph with more than 91 edges must be connected. Since $92 > 91$, this condition guarantees that $G$ is connected.
D) Every vertex in $G$ has a degree of at least 2. This is false. Consider a graph consisting of two disjoint cycles, say $C_7$ and $C_8$. This graph has $7+8=15$ vertices, and every vertex has degree 2. However, the graph is disconnected.
Answer: \boxed{C}"

---

Remember

> The maximum number of edges a disconnected graph with $n$ vertices can have is $\frac{(n-1)(n-2)}{2}$. Any graph with more edges than this must be connected.

---

---

Part 3: Matching and Colouring

Key Definitions

A subset of edges $M \subseteq E$ in a graph $G=(V, E)$ such that no two edges in $M$ share a common vertex.

• Maximum Matching: A matching with the largest possible number of edges.


• Perfect Matching: A matching that covers every vertex of the graph. A perfect matching can only exist if $|V|$ is even.

---

Essential Formulas

---

Must Remember

Fundamental Inequality: For any graph $G$, the relationship $\omega(G) \le \chi(G) \le \Delta(G) + 1$ holds. Use the lower bound $\omega(G)$ to establish a minimum number of colours and the upper bound $\Delta(G)+1$ as a maximum.

Bipartite Graphs are 2-Colourable: The most critical test for a bipartite graph is the absence of odd-length cycles. This is equivalent to being 2-colourable.

Greedy Colouring is Not Optimal: The greedy (sequential) colouring algorithm guarantees a proper colouring using at most $\Delta(G)+1$ colours. However, the number of colours used depends heavily on the vertex ordering and may not equal $\chi(G)$.

Matching Terminology: Do not confuse a maximal matching (one to which no more edges can be added) with a maximum matching (one with the most edges possible). A maximum matching is always maximal, but the reverse is not true.

---

Common Mistakes

❌ $\chi(G)$ is always equal to $\omega(G)$.
✅ Correct: $\chi(G) \ge \omega(G)$. For an odd cycle $C_5$, $\omega(C_5)=2$ but $\chi(C_5)=3$.

❌ The greedy algorithm finds the chromatic number.
✅ Correct: The greedy algorithm provides an upper bound on the chromatic number, i.e., colours used $\le \Delta(G)+1$. It is an approximation.

❌ If $\chi(G) = k$, the graph must contain a $K_k$ subgraph.
✅ Correct: A graph can be $k$-chromatic without containing a $K_k$. For example, $C_5$ is 3-chromatic but has no $K_3$.

---

Quick Practice

type="NAT" question="Consider the bipartite graph $G=(U \cup V, E)$ where $U=\{u_1, u_2, u_3, u_4\}$, $V=\{v_1, v_2, v_3, v_4\}$, and the edge set is $E = \{(u_1, v_1), (u_1, v_3), (u_2, v_1), (u_2, v_4), (u_3, v_2), (u_4, v_3), (u_4, v_4)\}$. What is the size of the maximum matching in $G$?" answer="4" hint="Try to find a set of edges with no common vertices that covers as many vertices as possible. Can you find a perfect matching?" solution="A perfect matching exists in this graph, for example: $M = \{(u_1, v_3), (u_2, v_1), (u_3, v_2), (u_4, v_4)\}$. Since a perfect matching covers all vertices, it is necessarily a maximum matching. The size of this matching is the number of edges, which is 4.
Answer: \boxed{4}"

type="MCQ" question="Let $G$ be a simple graph with 10 vertices, $\chi(G) = 5$, and $\Delta(G) = 8$. Which of the following statements is always true?" options=["A) $G$ contains a $K_5$ subgraph.", "B) The largest independent set in $G$ has size 2.", "C) G is not a planar graph.", "D) $G$ must contain an odd cycle."] answer="C" hint="Evaluate each option against the provided properties and standard theorems." solution="
A) False. We know $\chi(G) \ge \omega(G)$, so $\omega(G) \le 5$. It is not guaranteed that $\omega(G)=5$. For example, $C_5$ has $\chi(C_5)=3$ but $\omega(C_5)=2$.
B) False. We know $\chi(G) \ge \lceil n / \alpha(G) \rceil$. Substituting the given values, $5 \ge \lceil 10 / \alpha(G) \rceil$. This implies $10 / \alpha(G) \le 5$, which means $\alpha(G) \ge 2$. The largest independent set must have a size of at least 2, but it is not guaranteed to be exactly 2.
C) True. The Four Colour Theorem states that any planar graph is 4-colourable, i.e., $\chi(G) \le 4$. Since $\chi(G) = 5$ for this graph, it cannot be planar.
D) False. A graph with $\chi(G) = 5$ must contain an odd cycle (as otherwise it would be bipartite and $\chi(G)=2$). While this statement is true, option C is a stronger, more direct conclusion from the given chromatic number. The question asks what is always true based on the information. The fact that it's not planar is a direct consequence of $\chi(G)=5$.
Answer: \boxed{G \text{ is not a planar graph.}}"

---

Remember

> The key to solving most colouring problems is bounding the chromatic number using cliques, independence number, and max degree: $\omega(G) \le \chi(G) \le \Delta(G) + 1$.

See full notes for detailed explanations and proofs!

Chapter Summary

In this chapter, we have explored the fundamental principles of graph theory, a cornerstone of discrete mathematics and computer science. From the basic definitions of vertices and edges to the more complex properties of matching and colouring, these concepts provide a powerful framework for modelling and solving a wide array of problems. For the purpose of the GATE examination, we emphasize the following core concepts that must be thoroughly understood.

The Handshaking Lemma: For any undirected graph $G=(V, E)$, the sum of the degrees of all vertices is equal to twice the number of edges: $\sum_{v \in V} \deg(v) = 2|E|$. This fundamental property implies that the number of vertices with an odd degree must always be even.

Eulerian and Hamiltonian Paths/Circuits: We have established the precise conditions for their existence. A connected graph has an Eulerian circuit if and only if every vertex has an even degree. A graph has a Hamiltonian circuit if it contains a cycle that visits every vertex exactly once; while no simple necessary and sufficient condition exists, Dirac's and Ore's theorems provide important sufficient conditions.

Planarity and Euler's Formula: A graph is planar if it can be drawn in a plane without any edges crossing. For any connected planar graph with $v$ vertices, $e$ edges, and $f$ faces, Euler's formula holds: $v - e + f = 2$. From this, we derived crucial corollaries for simple graphs, such as $e \le 3v - 6$ for $v \ge 3$, which are instrumental in proving that certain graphs, like $K_5$ and $K_{3,3}$, are non-planar.

Graph Colouring: The chromatic number, $\chi(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that no two adjacent vertices share the same colour. We know that for any simple graph $G$, $\chi(G) \le \Delta(G) + 1$, where $\Delta(G)$ is the maximum degree of any vertex in $G$. A graph is bipartite if and only if its chromatic number is 2 (or 1 if it has no edges).

Matching in Bipartite Graphs: A matching is a subset of edges with no common vertices. A maximum matching contains the largest possible number of edges. In a bipartite graph, the size of the maximum matching is equal to the minimum number of vertices required to cover all edges (Kőnig's Theorem). Understanding the concept of an augmenting path is key to finding such a matching.

---

Chapter Review Questions

type="MCQ" question="Let $G$ be a simple, connected, planar graph with 10 vertices. It is known that the degree of each vertex is at least 3. What is the maximum possible number of edges in $G$?" options=["20","22","24","26"] answer="24" hint="Use the Handshaking Lemma to establish a lower bound on the number of edges. Then, use the inequality for planar graphs, $e \le 3v - 6$, to establish an upper bound." solution="Let $v$ be the number of vertices and $e$ be the number of edges. We are given $v=10$.
From the Handshaking Lemma, we have:

We are given that $\deg(v_i) \ge 3$ for all $i$. Therefore:

This implies $2e \ge 30$, or $e \ge 15$.

For a simple, connected planar graph with $v \ge 3$, we have the inequality:

Substituting $v=10$, we get:



Combining our two results, we have $15 \le e \le 24$. The maximum possible number of edges is therefore 24. This can be achieved, for instance, in an icosahedral graph which is planar, has 12 vertices, 30 edges, and is 5-regular. A planar graph with 10 vertices and 24 edges can also be constructed. Thus, the maximum possible value is 24.
Answer: \boxed{24}"

type="NAT" question="What is the chromatic number of the wheel graph $W_{12}$ (a graph with 12 vertices formed by connecting a central vertex to all vertices of a $C_{11}$ cycle)?" answer="4" hint="Consider the cycle part of the graph first. Then consider the central 'hub' vertex and its connections." solution="The wheel graph $W_{12}$ consists of a central vertex, say $v_0$, connected to all 11 vertices ($v_1, \dots, v_{11}$) of a cycle $C_{11}$.

First, let us determine the chromatic number of the subgraph formed by the cycle $C_{11}$. A cycle graph $C_n$ has a chromatic number $\chi(C_n)=2$ if $n$ is even, and $\chi(C_n)=3$ if $n$ is odd. Since $n=11$ is odd, we require 3 colours to properly colour the vertices of the cycle.

Let the colours used for the cycle be $\{c_1, c_2, c_3\}$.

The central vertex $v_0$ is adjacent to every vertex on the cycle $C_{11}$. Therefore, the colour assigned to $v_0$ must be different from the colours of all $v_1, \dots, v_{11}$.

Since colouring the cycle vertices already exhausts the set of colours $\{c_1, c_2, c_3\}$, we must introduce a new, fourth colour, say $c_4$, for the central vertex $v_0$.

With four colours, we can properly colour the graph: use three colours for the cycle and the fourth for the center. Since we have shown that at least four colours are necessary, the chromatic number is exactly 4.

Thus, $\chi(W_{12}) = 4$.
Answer: \boxed{4}"

type="MSQ" question="Which of the following statements about the complete bipartite graph $K_{4,6}$ is/are true?" options=["A) $K_{4,6}$ has an Eulerian circuit.", "B) $K_{4,6}$ is not planar.", "C) $K_{4,6}$ has a perfect matching.", "D) The chromatic number of $K_{4,6}$ is 4."] answer="A,B" hint="Check the properties one by one: degree of vertices for Eulerian circuit, Kuratowski's theorem for planarity, Hall's condition for matching, and the definition of bipartiteness for chromatic number." solution="Let $G = K_{4,6}$. The vertex set is partitioned into $V_1$ and $V_2$ with $|V_1|=4$ and $|V_2|=6$.

A. Eulerian Circuit: A connected graph has an Eulerian circuit if and only if every vertex has an even degree. In $K_{4,6}$, the 4 vertices in $V_1$ each have a degree of 6 (even). The 6 vertices in $V_2$ each have a degree of 4 (even). Since all vertex degrees are even and the graph is connected, $K_{4,6}$ has an Eulerian circuit. This statement is true.

B. Planarity: A graph is non-planar if it contains $K_5$ or $K_{3,3}$ as a minor (Kuratowski's Theorem). We can find a $K_{3,3}$ subgraph within $K_{4,6}$. To do this, select 3 vertices from $V_1$ and 3 vertices from $V_2$. The subgraph induced by these 6 vertices is $K_{3,3}$. Since $K_{4,6}$ contains $K_{3,3}$ as a subgraph, it is not planar. This statement is true.

C. Perfect Matching: A perfect matching is a matching that covers every vertex of the graph. For a perfect matching to exist, the graph must have an even number of vertices. $K_{4,6}$ has $4+6=10$ vertices, which is even. However, in a bipartite graph $K_{m,n}$, a perfect matching requires $m=n$. Here, $m=4$ and $n=6$. A matching can have at most $\min(m,n) = 4$ edges. This matching would cover all 4 vertices in $V_1$ and 4 out of 6 vertices in $V_2$. The remaining 2 vertices in $V_2$ would be unmatched. Therefore, $K_{4,6}$ does not have a perfect matching. This statement is false.

D. Chromatic Number: The chromatic number $\chi(G)$ of any bipartite graph with at least one edge is 2. We can colour all vertices in $V_1$ with one colour (e.g., red) and all vertices in $V_2$ with a second colour (e.g., blue). No two adjacent vertices will have the same colour. Therefore, $\chi(K_{4,6}) = 2$. The statement claims the chromatic number is 4. This statement is false.

The correct statements are A and B.
Answer: \boxed{A,B}"