GATE CS Chapter-wise PYQs

1. **Identify the graph:** The provided SVG diagram illustrates a graph with 8 vertices. Upon inspection of the edges, it is clear that every vertex is connected to every other vertex. This type of graph is known as a complete graph with $n$ vertices, denoted as $K_n$. In this case, since there are 8 vertices, the graph is $K_8$. 2. **Define chromatic number:** The chromatic number of a graph $G$, denoted as $\chi(G)$, is the minimum number of colors required to color the vertices of $G$ such that no two adjacent vertices share the same color. This is referred to as a proper coloring. 3. **Determine the chromatic number for a complete graph:** In a complete graph $K_n$, every vertex is adjacent to every other vertex. Therefore, to satisfy the condition of a proper coloring (i.e., no two adjacent vertices having the same color), each of the $n$ vertices must be assigned a unique color. Thus, the chromatic number of a complete graph $K_n$ is $n$. For the given graph, which is $K_8$, the chromatic number is 8. Answer: $\boxed{8}$

The problem states that $A$ is the adjacency matrix of a simple undirected graph $G$, and $A$ is its own inverse, meaning $A = A^{-1}$. This implies $A^2 = I$, where $I$ is the identity matrix. Let $A$ be an $n \times n$ adjacency matrix. For a simple undirected graph: 1. $A_{ii} = 0$ for all $i$ (no self-loops). 2. $A_{ij} = A_{ji}$ for all $i, j$ (symmetric matrix). 3. $A_{ij} \in \{0, 1\}$. We are given $A^2 = I$. Let's analyze the elements of $A^2$. The element in the $i$-th row and $j$-th column of $A^2$ is given by: **Step 1: Analyze the diagonal elements of $A^2$.** Since $A^2 = I$, the diagonal elements must be 1. So, $(A^2)_{ii} = 1$ for all $i = 1, \dots, n$. Since $A$ is symmetric, $A_{ki} = A_{ik}$. Since $A_{ii} = 0$ (no self-loops), the term $A_{ii}^2$ is 0. Since $A_{ik}$ can only be 0 or 1, $A_{ik}^2$ is also 0 or 1. The sum $\sum_{k \neq i} A_{ik}^2$ counts the number of neighbors of vertex $i$, which is its degree, $\deg(i)$. Therefore, we have: This means every vertex in the graph $G$ has a degree of exactly 1. **Step 2: Analyze the off-diagonal elements of $A^2$.** Since $A^2 = I$, the off-diagonal elements must be 0. So, $(A^2)_{ij} = 0$ for all $i \neq j$. The term $A_{ik} A_{kj}$ is 1 if there is an edge between $i$ and $k$ ($A_{ik}=1$) AND an edge between $k$ and $j$ ($A_{kj}=1$). This means there is a path of length 2 from $i$ to $j$ via vertex $k$. The sum $\sum_{k=1}^{n} A_{ik} A_{kj}$ represents the total number of paths of length 2 between vertex $i$ and vertex $j$. Since this sum must be 0 for all $i \neq j$, it implies that there are no paths of length 2 between any two distinct vertices $i$ and $j$. **Step 3: Combine the findings.** From Step 1, we know that every vertex in $G$ has a degree of 1. This means each vertex is connected to exactly one other vertex. Let's consider an arbitrary vertex $v$. Since $\deg(v) = 1$, $v$ is connected to exactly one other vertex, say $u$. So, there is an edge $(v, u)$. Now, consider any two distinct vertices $i$ and $j$. From Step 2, there are no paths of length 2 between $i$ and $j$. If $i$ is connected to $u$, then $u$ is its only neighbor. If $u$ were connected to any other vertex $j$ (where $j \neq i$), then there would be a path $i-u-j$ of length 2 between $i$ and $j$. But this contradicts our finding from Step 2. Therefore, if $i$ is connected to $u$, then $u$ cannot be connected to any vertex other than $i$. Since $\deg(u)=1$, $u$ must be connected only to $i$. This means that the graph $G$ consists of a collection of disjoint edges. Each vertex is part of exactly one edge. This is the definition of a perfect matching. **Step 4: Evaluate the given options.** * **"$G$ is a cycle"**: A cycle graph $C_n$ (for $n \ge 3$) has all vertices with degree 2. This contradicts our finding that every vertex has degree 1. * **"$G$ is a perfect matching"**: This perfectly matches our derivation. A perfect matching is a set of edges such that every vertex in the graph is incident to exactly one edge in the set. This implies every vertex has degree 1. * **"$G$ is a complete graph"**: A complete graph $K_n$ has all vertices with degree $n-1$. For $n-1=1$, $n=2$. $K_2$ is a single edge, which is a perfect matching. However, for $n > 2$, $K_n$ is not a perfect matching (e.g., $K_3$ has degree 2 for all vertices). So, this is not *always* true. * **"There is no such graph $G$"**: Such graphs exist. For example, a graph with two vertices and one edge ($K_2$) has $A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$. Then $A^2 = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I$. This is a perfect matching. Another example is two disjoint edges (a graph with 4 vertices and 2 edges). So, this statement is false. Based on the analysis, the only statement that is always true is that $G$ is a perfect matching. The final answer is $\boxed{\text{G is a perfect matching}}$.

Here's a step-by-step solution: 1. The given graph is a complete graph with 4 vertices, labelled A, B, C, and D. 2. For a complete graph with $n$ vertices, the number of spanning trees can be found using Cayley's Formula. 3. Cayley's Formula states that the number of spanning trees in a complete graph $K_n$ is $n^{n-2}$. 4. In this case, the number of vertices is $n=4$. 5. Substitute $n=4$ into Cayley's Formula: Answer: $\boxed{16}$

The problem describes a greedy vertex coloring algorithm and asks us to identify the true statements regarding its properties. Let's analyze each statement. The greedy coloring algorithm processes vertices in a given order $v_1, v_2, \dots, v_n$. For each vertex $v_i$, it assigns the smallest positive integer color $j$ that has not been used by any of its already-colored neighbors. **1. This procedure results in a proper vertex coloring of $G$.** A proper vertex coloring requires that no two adjacent vertices have the same color. When `color($v_i$)` is assigned, the algorithm explicitly chooses the smallest color $j$ such that no *already-colored* neighbor of $v_i$ has color $j$. This ensures that $v_i$ does not share a color with any of its neighbors $v_k$ where $k < i$. For any neighbor $v_k$ where $k > i$, when $v_k$ is processed, it will similarly choose a color different from its already-colored neighbors, including $v_i$. Therefore, for any edge $(v_i, v_k)$ in $G$, `color($v_i$)` will be different from `color($v_k$)`. This statement is **TRUE**. **2. The number of colors used is at most $\Delta(G) + 1$.** Let $v_i$ be any vertex in $G$. When $v_i$ is being colored, it has at most $\deg(v_i)$ neighbors. Let $N_i^-$ be the set of neighbors of $v_i$ that have already been colored (i.e., $N_i^- = \{v_k \in N(v_i) : k < i\}$). The algorithm assigns `color($v_i$)` to be the smallest positive integer not present in the set of colors used by $N_i^-$. The number of distinct colors used by vertices in $N_i^-$ is at most $|N_i^-|$. Since $|N_i^-| \le \deg(v_i)$ and $\deg(v_i) \le \Delta(G)$, the number of distinct colors used by $N_i^-$ is at most $\Delta(G)$. If $k$ distinct colors are used by $N_i^-$, then the smallest available color will be at most $k+1$. Thus, `color($v_i$)` will be at most $\deg(v_i) + 1$, which is at most $\Delta(G) + 1$. Since this holds for every vertex $v_i$, the total number of colors used in the graph is at most $\Delta(G) + 1$. This statement is **TRUE**. **3. The number of colors used is at most $\Delta(G)$.** Consider a complete graph $K_n$ with $n$ vertices. For $K_n$, $\Delta(K_n) = n-1$. Let the vertex ordering be $v_1, v_2, \dots, v_n$. - `color($v_1$)` = 1. - `color($v_2$)`: $v_2$ is adjacent to $v_1$ (color 1). So `color($v_2$)` = 2. - `color($v_3$)`: $v_3$ is adjacent to $v_1$ (color 1) and $v_2$ (color 2). So `color($v_3$)` = 3. - ... - `color($v_n$)`: $v_n$ is adjacent to $v_1, \dots, v_{n-1}$ (colors $1, \dots, n-1$). So `color($v_n$)` = $n$. The number of colors used is $n$. Since $n = \Delta(K_n) + 1$, the number of colors used is not at most $\Delta(K_n)$ for $n > 1$. For example, for $K_2$, $\Delta(K_2)=1$, but 2 colors are used. $2 \not\le 1$. This statement is **FALSE**. **4. The number of colors used is equal to the chromatic number of $G$.** The chromatic number $\chi(G)$ is the minimum number of colors required for a proper vertex coloring. The greedy algorithm does not always produce an optimal coloring. The number of colors used by the greedy algorithm depends on the chosen vertex ordering. Consider the following graph $G$ with vertices $v_1, v_2, v_3, v_4, v_5$ and edges $(v_1, v_2), (v_1, v_3), (v_2, v_4), (v_3, v_4), (v_4, v_5)$. This graph is bipartite, so its chromatic number $\chi(G) = 2$. Let's apply the greedy algorithm with the vertex ordering $v_1, v_5, v_2, v_3, v_4$. 1. `color($v_1$)` = 1. 2. `color($v_5$)` = 1 (since $v_5$ is not adjacent to $v_1$). 3. `color($v_2$)`: Neighbor $v_1$ has color 1. So `color($v_2$)` = 2. 4. `color($v_3$)`: Neighbor $v_1$ has color 1. So `color($v_3$)` = 2. 5. `color($v_4$)`: Neighbors are $v_2$ (color 2), $v_3$ (color 2), and $v_5$ (color 1). The set of colors used by its neighbors is $\{1, 2\}$. The smallest available color is 3. So `color($v_4$)` = 3. In this case, the greedy algorithm used 3 colors, but $\chi(G) = 2$. Since $3 \ne 2$, the number of colors used is not always equal to the chromatic number of $G$. This statement is **FALSE**. Based on the analysis, statements 1 and 2 are TRUE. The final answer is $\boxed{\text{Statements 1 and 2 are TRUE}}$.

Solution: To find the maximum number of edges in a disconnected undirected graph with $n=10$ vertices, we consider the structure of such a graph. 1. **Understanding Disconnected Graphs:** A graph is disconnected if it can be partitioned into two or more non-empty sets of vertices such that there are no edges connecting vertices from different sets. To maximize the number of edges, we want to minimize the number of components, ideally having exactly two components, and make these components as dense as possible (i.e., complete graphs). 2. **Partitioning Vertices:** Let the $n$ vertices be partitioned into two non-empty sets, $V_1$ and $V_2$, with $|V_1| = k$ and $|V_2| = n-k$. For the graph to be disconnected, there must be no edges between $V_1$ and $V_2$. To maximize the total number of edges, we assume that the subgraphs induced by $V_1$ and $V_2$ are complete graphs, $K_k$ and $K_{n-k}$ respectively. 3. **Number of Edges:** The number of edges in a complete graph $K_m$ is $\binom{m}{2} = \frac{m(m-1)}{2}$. Thus, the total number of edges in our disconnected graph, with components $K_k$ and $K_{n-k}$, would be: For $n=10$, this becomes: We need to maximize this value for $1 \le k \le 9$ (since both components must be non-empty). 4. **Evaluating for different values of $k$:** * For $k=1$: One component is $K_1$ (an isolated vertex), and the other is $K_9$. * For $k=2$: One component is $K_2$, and the other is $K_8$. * For $k=3$: One component is $K_3$, and the other is $K_7$. * For $k=4$: One component is $K_4$, and the other is $K_6$. * For $k=5$: One component is $K_5$, and the other is $K_5$. 5. **Conclusion:** The function $E(k)$ is maximized when $k$ is as far from $n/2$ as possible, i.e., when $k=1$ (or $k=n-1=9$ by symmetry). The maximum number of edges is $36$. This configuration corresponds to a graph where one component is a complete graph on $9$ vertices ($K_9$) and the other component is a single isolated vertex ($K_1$). The maximum number of edges a disconnected graph of $10$ vertices can have is $36$. Answer: $\boxed{36}$

**Solution:** Let $\mathbf{A}$ be the adjacency matrix of a simple undirected unweighted graph with $n$ vertices. 1. **Analyze Option 1:** "The diagonal entries of $\mathbf{A}^2$ are the degrees of the vertices of the graph." Let $\mathbf{A}_{ij}$ be the entry in the $i$-th row and $j$-th column of $\mathbf{A}$. For a simple undirected graph, $\mathbf{A}_{ii} = 0$ (no self-loops) and $\mathbf{A}_{ij} = \mathbf{A}_{ji}$ (undirected). Also, $\mathbf{A}_{ij} \in \{0, 1\}$. The $(i, i)$-th entry of $\mathbf{A}^2$ is given by the sum of products of entries from the $i$-th row of $\mathbf{A}$ and the $i$-th column of $\mathbf{A}$: Since $\mathbf{A}$ is symmetric for an undirected graph, $\mathbf{A}_{ki} = \mathbf{A}_{ik}$. Substituting this into the equation: Since $\mathbf{A}_{ik}$ can only be $0$ or $1$, $(\mathbf{A}_{ik})^2 = \mathbf{A}_{ik}$. The sum $\sum_{k=1}^{n} \mathbf{A}_{ik}$ represents the number of edges incident to vertex $i$, which is the definition of the degree of vertex $i$, $\operatorname{deg}(v_i)$. Thus, the diagonal entries of $\mathbf{A}^2$ are indeed the degrees of the vertices of the graph. This statement is **TRUE**. 2. **Analyze Option 2:** "If the graph is connected, then none of the entries of $\mathbf{A}^{n-1}+\mathbf{I}_n$ can be zero." The $(i, j)$-th entry of $\mathbf{A}^k$ represents the number of walks of length $k$ from vertex $i$ to vertex $j$. Consider a path graph $P_n$ with $n$ vertices, $v_1 - v_2 - \dots - v_n$. This graph is connected. Let's take $n=3$. The graph is $v_1 - v_2 - v_3$. The adjacency matrix $\mathbf{A}$ is: We need to compute $\mathbf{A}^{n-1}$, which is $\mathbf{A}^2$ for $n=3$: Now, let's compute $\mathbf{A}^{n-1} + \mathbf{I}_n = \mathbf{A}^2 + \mathbf{I}_3$: The entry at position $(1, 2)$ is $0$. This contradicts the statement that "none of the entries of $\mathbf{A}^{n-1}+\mathbf{I}_n$ can be zero." This statement is **FALSE**. 3. **Analyze Option 3:** "If the sum of all the elements of $\mathbf{A}$ is at most $2(n-1)$, then the graph must be acyclic." The sum of all elements of $\mathbf{A}$ is $2m$, where $m$ is the number of edges in the graph (since $\mathbf{A}$ is symmetric and has $0$s on the diagonal for a simple graph). The given condition is $2m \le 2(n-1)$, which simplifies to $m \le n-1$. A graph with $n$ vertices and $m$ edges is acyclic if and only if it is a forest (a collection of trees). If $m < n-1$, the graph must be disconnected and is a forest, hence acyclic. If $m = n-1$: - If the graph is connected, it is a tree, which is acyclic. - If the graph is disconnected, it must contain a cycle. For example, consider $n=4$ vertices and $m=3$ edges. A graph consisting of a $C_3$ (cycle of length 3) and an isolated vertex is disconnected and has $3$ edges. Let the vertices be $v_1, v_2, v_3, v_4$. Edges are $(v_1, v_2), (v_2, v_3), (v_3, v_1)$. Vertex $v_4$ is isolated. This graph has $n=4$ vertices and $m=3$ edges, so $m=n-1$. However, it contains a cycle ($v_1-v_2-v_3-v_1$). Since a graph with $m=n-1$ edges can be disconnected and contain a cycle, the statement "the graph must be acyclic" is not always true. This statement is **FALSE**. 4. **Analyze Option 4:** "If there is at least a $1$ in each of $\mathbf{A}$'s rows and columns, then the graph must be connected." Having at least a $1$ in each row (and column, due to symmetry) means that every vertex has a degree of at least $1$. In other words, there are no isolated vertices. Consider a graph with $n=4$ vertices and two disjoint edges: $v_1-v_2$ and $v_3-v_4$. The adjacency matrix $\mathbf{A}$ is: Each row and column of $\mathbf{A}$ contains at least one $1$. For example, row 1 has $\mathbf{A}_{12}=1$, row 2 has $\mathbf{A}_{21}=1$, row 3 has $\mathbf{A}_{34}=1$, and row 4 has $\mathbf{A}_{43}=1$. However, this graph is disconnected (it has two connected components: $\{v_1, v_2\}$ and $\{v_3, v_4\}$). Therefore, having no isolated vertices does not guarantee that the graph is connected. This statement is **FALSE**. Based on the analysis, only Option 1 is true. Answer: \boxed{The diagonal entries of $\mathbf{A}^2$ are the degrees of the vertices of the graph.}

**Step 1: Analyze the Peterson Graph.** The Peterson graph is a 3-regular graph with 10 vertices and 15 edges. It consists of an outer 5-cycle ($C_5$) and an inner 5-cycle (often drawn as a 5-pointed star), with corresponding vertices connected by "spokes". Let the outer vertices be $v_0, v_1, v_2, v_3, v_4$ and the inner vertices be $u_0, u_1, u_2, u_3, u_4$. The edges are: 1. Outer cycle edges: $(v_i, v_{i+1 \pmod 5})$ for $i \in \{0, 1, 2, 3, 4\}$. 2. Spoke edges: $(v_i, u_i)$ for $i \in \{0, 1, 2, 3, 4\}$. 3. Inner star edges: $(u_i, u_{i+2 \pmod 5})$ for $i \in \{0, 1, 2, 3, 4\}$. **Step 2: Evaluate Option 1 - The chromatic number of the graph is 3.** The Peterson graph contains a $C_5$ (e.g., the outer pentagon $v_0-v_1-v_2-v_3-v_4-v_0$). Since $C_5$ is an odd cycle, the graph is not bipartite, and its chromatic number $\chi(G)$ must be at least 3. To show $\chi(G)=3$, we need to find a valid 3-coloring. Let's assign colors (1, 2, 3) to the vertices: 1. Color the outer pentagon: $c(v_0)=1$ $c(v_1)=2$ $c(v_2)=3$ $c(v_3)=1$ $c(v_4)=2$ (This ensures no adjacent outer vertices have the same color). 2. Color the inner pentagon, respecting connections to outer vertices and inner star edges: * $c(u_0)$ must be $\ne c(v_0)=1$. Let $c(u_0)=2$. * $c(u_1)$ must be $\ne c(v_1)=2$. * $c(u_2)$ must be $\ne c(v_2)=3$. * $c(u_3)$ must be $\ne c(v_3)=1$. * $c(u_4)$ must be $\ne c(v_4)=2$. Now consider the inner star edges $(u_i, u_{i+2 \pmod 5})$: * Since $u_0$ is adjacent to $u_2$ and $u_3$, and $c(u_0)=2$: * $c(u_2) \ne 2$. From $c(u_2) \ne 3$, we must have $c(u_2)=1$. * $c(u_3) \ne 2$. From $c(u_3) \ne 1$, we must have $c(u_3)=3$. * Now we have $c(u_0)=2, c(u_2)=1, c(u_3)=3$. * Consider $u_4$: It is adjacent to $u_1$ and $u_2$. Since $c(u_2)=1$, $c(u_4) \ne 1$. From $c(u_4) \ne 2$, we must have $c(u_4)=3$. * Consider $u_1$: It is adjacent to $u_3$ and $u_4$. Since $c(u_3)=3$ and $c(u_4)=3$, $c(u_1)$ must be $\ne 3$. From $c(u_1) \ne 2$, we must have $c(u_1)=1$. Let's verify the complete coloring: * Outer: $c(v_0)=1, c(v_1)=2, c(v_2)=3, c(v_3)=1, c(v_4)=2$. * Inner: $c(u_0)=2, c(u_1)=1, c(u_2)=1, c(u_3)=3, c(u_4)=3$. Check all adjacencies: * Outer edges: $(v_0,v_1): (1,2)$, $(v_1,v_2): (2,3)$, $(v_2,v_3): (3,1)$, $(v_3,v_4): (1,2)$, $(v_4,v_0): (2,1)$. All OK. * Spoke edges: $(v_0,u_0): (1,2)$, $(v_1,u_1): (2,1)$, $(v_2,u_2): (3,1)$, $(v_3,u_3): (1,3)$, $(v_4,u_4): (2,3)$. All OK. * Inner star edges: $(u_0,u_2): (2,1)$, $(u_1,u_3): (1,3)$, $(u_2,u_4): (1,3)$, $(u_3,u_0): (3,2)$, $(u_4,u_1): (3,1)$. All OK. Since a 3-coloring exists, and $\chi(G) \ge 3$, the chromatic number of the Peterson graph is 3. This statement is **TRUE**. **Step 3: Evaluate Option 2 - The graph has a Hamiltonian path.** A Hamiltonian path is a path that visits every vertex exactly once. The Peterson graph is known to not have a Hamiltonian cycle, but it does have a Hamiltonian path. One example of a Hamiltonian path is: $v_0 - v_1 - v_2 - v_3 - v_4 - u_4 - u_1 - u_3 - u_0 - u_2$ Let's verify this path: * $v_0 \to v_1$ (outer edge) * $v_1 \to v_2$ (outer edge) * $v_2 \to v_3$ (outer edge) * $v_3 \to v_4$ (outer edge) * $v_4 \to u_4$ (spoke edge) * $u_4 \to u_1$ (inner star edge, $u_4$ is adjacent to $u_{4+2 \pmod 5} = u_1$) * $u_1 \to u_3$ (inner star edge, $u_1$ is adjacent to $u_{1+2 \pmod 5} = u_3$) * $u_3 \to u_0$ (inner star edge, $u_3$ is adjacent to $u_{3+2 \pmod 5} = u_0$) * $u_0 \to u_2$ (inner star edge, $u_0$ is adjacent to $u_{0+2 \pmod 5} = u_2$) This path visits all 10 vertices exactly once. This statement is **TRUE**. **Step 4: Evaluate Option 3 - The following graph is isomorphic to the Peterson graph.** Isomorphic graphs must have the same number of vertices and edges. * The Peterson graph has 10 vertices and 15 edges. * The graph provided in the option has: * 8 outer vertices (forming an octagon). * 2 inner vertices. * Total vertices = $8 + 2 = 10$. (Matches Peterson graph) * Edges: * 8 edges for the outer octagon. * 4 edges connecting the top inner vertex to outer vertices. * 4 edges connecting the bottom inner vertex to outer vertices. * 1 edge connecting the two inner vertices. * Total edges = $8 + 4 + 4 + 1 = 17$. Since the number of edges (17) in the given graph is different from the number of edges in the Peterson graph (15), the two graphs are not isomorphic. This statement is **FALSE**. **Step 5: Evaluate Option 4 - The size of the largest independent set of the given graph is 3.** An independent set is a set of vertices where no two vertices are adjacent. The size of the largest independent set is denoted by $\alpha(G)$. Let's try to find an independent set of size 4 in the Peterson graph. Consider the set $S = \{v_0, v_2, v_4, u_1\}$. * $v_0, v_2, v_4$ are non-adjacent (they are vertices of the outer $C_5$ separated by one vertex). * Check adjacencies between $u_1$ and $\{v_0, v_2, v_4\}$: * $u_1$ is adjacent to $v_1$, $u_3$, $u_4$. * $u_1$ is not adjacent to $v_0$. * $u_1$ is not adjacent to $v_2$. * $u_1$ is not adjacent to $v_4$. * Therefore, the set $S = \{v_0, v_2, v_4, u_1\}$ is an independent set of size 4. Since we found an independent set of size 4, the largest independent set must be at least 4. It is a known property that the independence number of the Peterson graph is 4. Therefore, the statement that the size of the largest independent set is 3 is incorrect. This statement is **FALSE**. **Conclusion:** Statements 1 and 2 are TRUE. The final answer is $\boxed{\text{The chromatic number of the graph is 3., The graph has a Hamiltonian path.}}$