Question 1
An undirected graph $G$ has 20 vertices and the degree of each vertex is at least 3 and at most 5. Which of the following statements is true regarding the graph $G$?
(a) The minimum number of edges that the graph $G$ can have is 60.
(b) The maximum number of edges that the graph $G$ can have is 100.
(c) The maximum number of edges that the graph $G$ can have is 60.
(d) The minimum number of edges that the graph $G$ can have is 30.
Solution:
Minimum edges: If every vertex has degree 3, sum of degrees is $20 \times 3 = 60$. Number of edges is $\frac{60}{2} = 30$.
Maximum edges: If every vertex has degree 5, sum of degrees is $20 \times 5 = 100$. Number of edges is $\frac{100}{2} = 50$.
Correct option: (d) The minimum number of edges that the graph $G$ can have is 30.
Question 2
If $G$ is a connected undirected graph such that every vertex has degree at most $k$, and the shortest path between any two vertices has length at most 2, then the number of vertices in $G$ can be at most
(a) $k^{2}-1$
(b) $k^{2}+1$
(c) $k^{2}$
(d) $k^{2}-k$
Solution:
BFS tree argument: Start with vertex $u$. At most $k$ neighbors (level 1). Each neighbor can have at most $k-1$ new neighbors (level 2).
Total vertices: $1 + k + k(k-1) = k^2 + 1$.
Correct option: (b) $k^{2}+1$.
Question 3
Suppose $A$ is the adjacency matrix of a connected undirected graph $G$. If $A^{2}=\left[\begin{array}{llllll}1 & 1 & 1 & 0 & 1 & 1 \ 1 & 1 & 1 & 1 & 0 & 1 \ 1 & 1 & 1 & 1 & 1 & 0 \ 0 & 1 & 1 & 1 & 1 & 1 \ 1 & 0 & 1 & 1 & 1 & 1 \ 1 & 1 & 0 & 1 & 1 & 1\end{array}\right]$ and the shortest path between any two vertices has length at most 2, then which of the following may represent the graph $G$?
Solution:
Analysis: The given matrix for $A^2$ implies that every pair of vertices is connected by a path of length at most 2, but not all pairs are directly connected.
Option (C) is correct (though the actual graph is not shown, the reasoning matches standard graph theory for such matrices).
Option (d) is incorrect because its $A^2$ is not as given.
Correct option: (C) (as per the solution, though the actual graph is not specified).
2. Multiple Select Questions
Question 4
Suppose in a farewell party of IIT Madras Mathematics department, 60 students were present. As in normal parties, handshaking took place and of course no one shook their own hand. The number of students who have made odd number of handshakes is $x$. Which of the followings can be a possible value of $x$?
(a) 6
(b) 13
(c) 21
(d) 28
Solution:
Handshake theorem: The number of vertices with odd degree is always even.
Possible values: $x$ must be even.
Correct options: (a) 6, (d) 28.
Question 5
Suppose $G$ is a graph with 6 vertices $0,1,2,3,4,5$ and the adjacency matrix of the graph $G$ is
Which of the following statements is True?
(a) The graph $G$ is a directed acyclic graph.
(b) From vertex 4, every other vertex is reachable.
(c) The longest path in the graph $G$ has length 4, in terms of number of edges.
(d) The longest path in the graph is $4 \rightarrow 0 \rightarrow 2 \rightarrow 3$.
Solution:
(a): $G$ is a directed acyclic graph (DAG) — True.
(b): From vertex 4, every other vertex is reachable — True (as per BFS tree drawn).
(c): Longest path has length 4 — False (no path of length 4 exists).
(d): Longest path is $4 \rightarrow 0 \rightarrow 2 \rightarrow 3$ — True (but note: as per adjacency matrix, the longest path is $4 \rightarrow 0 \rightarrow 2 \rightarrow 3$, but the matrix does not show a direct edge from 2 to 3; however, as per the solution, this is considered the longest path).
Correct options: (a), (b), (d) (but based on the adjacency matrix, (d) is only true if there is a path as stated; in the given matrix, vertex 0 connects to 2, and 2 connects to 3, so this is a valid path. The solution marks (d) as correct, but (c) is incorrect.)
Question 6
Which of the following statements is(are) true?
(a) Every directed acyclic graph has a vertex with outdegree 0.
(b) In a directed acyclic graph, the longest path between a pair of vertices is always unique.
(c) If an undirected graph $G$ is connected, then the graph representing the transitive closure of the graph $G$ is a complete graph.
(d) Suppose $A$ is the adjacency matrix of a graph $G$ with $n$ vertices, any non-zero entry $(i, j)$ in the matrix $A^{k}$, where $k<n$, indicates that there is a path of length $k$ from vertex $i$ to vertex $j$.
Solution:
(a): Every DAG has a vertex with outdegree 0 — True.
(b): Longest path in a DAG is not always unique — False.
(c): Transitive closure of a connected undirected graph is a complete graph — True.
(d): Non-zero entry in $A^k$ indicates a path of length $k$ — True.
Correct options: (a), (c), (d).
3. Use the Following Information for Questions [7-8]
Shreya needs to perform 10 tasks ${A, B, C, D, \ldots, J}$. Some tasks need to be performed after a particular task. The table shows each task and the set of tasks that can be performed only after it:
Task
Tasks after it
A
${B, E, G}$
B
${F, H}$
C
${E, F, I}$
D
${F, I}$
E
${G}$
F
${H, J}$
G
${J}$
H
${G, J}$
I
${J}$
J
$\emptyset$
Question 7
Which of the following sequences may represent the possible order in which Shreya can perform the tasks?
(a) $A, C, B, D, E, I, F, H, G, J$
(b) $A, D, C, B, E, I, F, H, G, J$
(c) $C, A, D, E, B, I, F, G, H, J$
(d) $D, C, A, B, E, I, F, H, G, J$
Solution:
Topological sort: Any sequence that respects the dependencies is valid.
(a): Valid topological order.
(b): Valid topological order.
(c): Invalid (task $G$ cannot be performed before $H$).
(d): Valid topological order.
Correct options: (a), (b), (d).
Question 8
If each task takes 5 minutes to complete and she performs all the independent tasks simultaneously, then the time (in minutes) taken by Shreya to complete all the tasks is
Solution:
Longest path: The critical path (longest sequence) is $A \rightarrow B \rightarrow F \rightarrow H \rightarrow G \rightarrow J$ or similar, but the solution lists the longest path lengths to each node as:
$A, C, D$: 0
$B, E, I$: 1
$F$: 2
$H$: 3
$G$: 4
$J$: 5
Time: Each step takes 5 minutes. The total time is $5 \times 6 = 30$ minutes (as per the solution, but this seems to consider the maximum path length, not the number of steps in the critical path; the solution adds 5 minutes for each “level” of the DAG, but the calculation is unclear. However, the answer given is 30.)
Answer: 30
4. Numerical Answer Type
Question 9
Suppose $R$ is a relation defined on a set $S$ and it is represented by a graph $G$ with edges ${(1,2), (2,3), (3,4), (4,5)}$. Find the number of edges that need to be added to the graph $G$ such that the new graph obtained after adding the edges represents a transitive relation.
