GATE CS Chapter Practice

**Step 1: Determine the number of vertices for each degree in $G$.** Let $n$ be the total number of vertices, so $n=9$. Let $n_3$ be the number of vertices with degree 3. Let $n_4$ be the number of vertices with degree 4. From the problem statement, we know that: 1. $n_3 + n_4 = n = 9$ 2. There are twice as many vertices of degree 3 as there are vertices of degree 4, so $n_3 = 2n_4$. Substitute the second equation into the first: Now, find $n_3$: So, graph $G$ has 6 vertices of degree 3 and 3 vertices of degree 4. **Step 2: Calculate the total number of edges in $G$.** Using the Handshaking Lemma, the sum of the degrees of all vertices is equal to twice the number of edges ($2|E|$). Substitute the calculated number of vertices for each degree: Thus, the graph $G$ has 15 edges. **Step 3: Calculate the total possible number of edges in a simple graph with $n$ vertices.** The maximum number of edges in a simple undirected graph with $n$ vertices (a complete graph $K_n$) is given by the formula $\frac{n(n-1)}{2}$. For $n=9$: **Step 4: Calculate the number of edges in the complement graph $\bar{G}$.** The complement graph $\bar{G}$ contains all the edges that are NOT present in $G$, from the set of all possible edges. Therefore, the number of edges in $\bar{G}$, denoted as $|\bar{E}|$, is: The number of edges in the complement graph $\bar{G}$ is 21. **Answer:** $\boxed{21}$

**Step 1: Understand the relationship between degrees in a graph and its complement.** For any simple undirected graph $G$ with $n$ vertices, and its complement graph $\bar{G}$, the degree of any vertex $v$ in $G$ and $\bar{G}$ are related by the formula: This is because a vertex $v$ is connected to all other $n-1$ vertices in the complete graph $K_n$. In $G$, it is connected to $\operatorname{deg}_G(v)$ vertices. In $\bar{G}$, it is connected to the remaining $(n-1) - \operatorname{deg}_G(v)$ vertices. In this problem, $n=8$, so $\operatorname{deg}_{\bar{G}}(v) = 7 - \operatorname{deg}_G(v)$. **Step 2: Express $S_{\bar{G}}$ in terms of $S_G$ and other graph parameters.** The sum of the squares of the degrees in $\bar{G}$ is $S_{\bar{G}} = \sum_{v \in V} \operatorname{deg}_{\bar{G}}(v)^2$. Substituting the relationship from Step 1: Expand the square term: Separate the summation: We know that $\sum_{v \in V} (n-1)^2 = n(n-1)^2$ (since $(n-1)^2$ is a constant for the summation). Also, $\sum_{v \in V}\operatorname{deg}_G(v)^2 = S_G$. From the Handshaking Lemma, $\sum_{v \in V}\operatorname{deg}_G(v) = 2|E|$, where $|E|$ is the number of edges in $G$. Substitute these into the equation for $S_{\bar{G}}$: **Step 3: Substitute the given values and solve for $|E|$.** Given values are: $n=8$, $S_G = 72$, $S_{\bar{G}} = 128$. Substitute these into the derived formula: Combine the constant terms: Rearrange the equation to solve for $|E|$: **Answer:** The number of edges in $G$ is $\boxed{12}$.

**Step 1: Determine the minimum number of edges ($E_{\text{min}}$).** For a simple undirected graph with $N$ vertices and $K$ connected components, the minimum number of edges required to ensure connectivity within each component is $N-K$. This occurs when each connected component is a tree (a connected graph with no cycles, having $v_i-1$ edges for $v_i$ vertices). Given $N=12$ and $K=4$: **Step 2: Determine the maximum number of edges ($E_{\text{max}}$).** To maximize the number of edges while maintaining $K$ connected components, we should make $K-1$ components as small as possible (i.e., isolated vertices, each contributing 0 edges), and consolidate the remaining vertices into a single large component that is a complete graph. A complete graph has the maximum possible number of edges for its given number of vertices. Number of isolated vertex components = $K-1 = 4-1 = 3$. These 3 components contribute $3 \times 1 = 3$ vertices and $3 \times 0 = 0$ edges. Number of vertices in the largest component = $N - (K-1) = 12 - 3 = 9$. This largest component, being a complete graph $K_9$, will have the maximum number of edges possible for 9 vertices. The number of edges in a complete graph with $v$ vertices is $\frac{v(v-1)}{2}$. Number of edges in the largest component: Therefore, the maximum number of edges $E_{\text{max}}$ is the sum of edges from all components: **Step 3: Calculate the difference $E_{\text{max}} - E_{\text{min}}$.** The difference between the maximum and minimum possible number of edges is 28. **Answer:** $\boxed{28}$

**Step 1: Understand the graph structure (King's Graph).** The graph described is commonly known as a King's graph. In this graph, each vertex $(i,j)$ is adjacent to all its 8 neighbors (including diagonals) on the chessboard, provided they are within the $m \times n$ grid. Specifically, a vertex $(i,j)$ is adjacent to $(i',j')$ if $i' \in \{i-1, i, i+1\}$, $j' \in \{j-1, j, j+1\}$, and $(i,j) \neq (i',j')$. **Step 2: Determine a lower bound for the chromatic number.** Since $m \ge 2$ and $n \ge 2$, we can always find a $2 \times 2$ subgrid within the $m \times n$ chessboard. Consider the four vertices $(i,j)$, $(i+1,j)$, $(i,j+1)$, $(i+1,j+1)$ for any $1 \le i < m$ and $1 \le j < n$. Each of these four vertices is adjacent to every other vertex in this set. For example, $(i,j)$ is adjacent to $(i+1,j)$ because $|i-(i+1)|=1 \le 1$ and $|j-j|=0 \le 1$. Similarly, $(i,j)$ is adjacent to $(i,j+1)$ and $(i+1,j+1)$. All pairs of these four vertices satisfy the adjacency condition. Thus, these four vertices form a complete graph $K_4$ as a subgraph. Since $G$ contains $K_4$ as a subgraph, any proper coloring of $G$ must assign distinct colors to the vertices of this $K_4$. Therefore, the chromatic number $\chi(G)$ must be at least 4. **Step 3: Determine an upper bound for the chromatic number (provide a 4-coloring).** We need to demonstrate that $G$ can be properly colored using at most 4 colors. Consider the following coloring scheme for each vertex $(i,j)$ using colors from the set $\{1, 2, 3, 4\}$: Let's analyze this coloring: * If $i-1$ is even and $j-1$ is even, $c(i,j) = 0 \times 2 + 0 + 1 = 1$. * If $i-1$ is even and $j-1$ is odd, $c(i,j) = 0 \times 2 + 1 + 1 = 2$. * If $i-1$ is odd and $j-1$ is even, $c(i,j) = 1 \times 2 + 0 + 1 = 3$. * If $i-1$ is odd and $j-1$ is odd, $c(i,j) = 1 \times 2 + 1 + 1 = 4$. This scheme creates a repeating $2 \times 2$ pattern of colors across the grid: Now, let's verify if this is a proper coloring. Consider any vertex $(i,j)$ with color $C = c(i,j)$. Its neighbors $(i',j')$ satisfy $i' \in \{i-1, i, i+1\}$ and $j' \in \{j-1, j, j+1\}$, excluding $(i,j)$ itself. The parities of $(i'-1)$ and $(j'-1)$ will cover all four combinations of (even/odd, even/odd) values relative to $(i-1)$ and $(j-1)$. For example, if $(i-1)$ is even, then $(i-1)-1$ is odd, $(i-1)$ is even, and $(i+1)-1$ is odd. Similarly for $j$. This implies that for any vertex $(i,j)$, its neighbors $(i',j')$ will have $( (i'-1) \pmod 2, (j'-1) \pmod 2 )$ values that correspond to all four possible combinations of $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$. Consequently, a vertex $(i,j)$ with color $C$ will have neighbors of all colors other than $C$. For instance, if $c(i,j)=1$ (meaning $(i-1) \pmod 2 = 0$ and $(j-1) \pmod 2 = 0$), its neighbors will include vertices with colors $2,3,4$. No neighbor will have color 1. This holds for any color $C \in \{1,2,3,4\}$. Therefore, this 4-coloring is a proper vertex coloring, which means $\chi(G) \le 4$. **Step 4: Conclude the chromatic number.** From Step 2, we established that $\chi(G) \ge 4$. From Step 3, we showed that $\chi(G) \le 4$. Combining these two bounds, we conclude that the chromatic number of the King's graph for $m \ge 2$ and $n \ge 2$ is exactly 4. The final answer is $\boxed{4}$.

Let $n$ be the total number of vertices in the graph $G$. **Step 1: Analyze the given degree constraints and apply the Handshaking Lemma.** The problem states that $G$ has at least one vertex of degree 5 and at least one vertex of degree 7. All other $n-2$ vertices have a degree of 2. The sum of degrees of all vertices in $G$ can be expressed as: According to the Handshaking Lemma, the sum of degrees in any graph must be an even number. In this case, $2n+8$ is always an even number for any integer $n$, so this condition is satisfied for any $n \ge 2$. **Step 2: Apply the property of maximum degree in a simple graph.** For a simple undirected graph with $n$ vertices, the degree of any vertex cannot exceed $n-1$. That is, $\deg(v) \le n-1$ for all $v \in V$. In the given graph, the highest degree specified is 7 (from the vertex of degree 7). Therefore, we must have: **Step 3: Determine the minimum value of $n$.** From the inequality $7 \le n-1$, we can deduce: This means that the minimum possible number of vertices $n$ must be 8. To confirm, if $n=8$, the degree sequence would include one vertex of degree 7, one of degree 5, and $8-2=6$ vertices of degree 2. The sequence would be $(7, 5, 2, 2, 2, 2, 2, 2)$. The sum of degrees is $7+5+6 \times 2 = 12+12 = 24$, which is even. The maximum degree is 7, and $n-1 = 8-1=7$, so $d_{max} \le n-1$ is satisfied. Such a graph can exist (e.g., by using the Havel-Hakimi theorem, though explicit construction is not required for this problem). Thus, the minimum possible value of $n$ is 8. The final answer is $\boxed{8}$

**Step 1: Analyze Option 1** According to the Handshaking Lemma, the sum of the degrees of all vertices in a graph is equal to twice the number of edges: This implies that the sum of degrees is always an even number. Let $V_{odd}$ be the set of vertices with an odd degree, and $V_{even}$ be the set of vertices with an even degree. The sum of degrees can be written as: Since each $\operatorname{deg}(v)$ for $v \in V_{even}$ is an even number, their sum $\sum_{v \in V_{even}} \operatorname{deg}(v)$ is also an even number. As the total sum $\sum_{v \in V} \operatorname{deg}(v)$ is even, it follows that $\sum_{v \in V_{odd}} \operatorname{deg}(v)$ must also be an even number. The sum of an odd number of odd integers is odd, while the sum of an even number of odd integers is even. Since $\sum_{v \in V_{odd}} \operatorname{deg}(v)$ is an even number, the number of terms in this sum, which is $|V_{odd}|$, must be even. Therefore, the number of vertices with an odd degree is always even. Option 1 is TRUE. **Step 2: Analyze Option 2** A simple undirected graph has no self-loops and no multiple edges between the same pair of vertices. The maximum number of edges in such a graph occurs when every distinct pair of vertices is connected by exactly one edge. Such a graph is called a complete graph, denoted $K_n$. The number of edges in a complete graph $K_n$ is the number of ways to choose 2 vertices from $n$ vertices, which is given by the binomial coefficient $\binom{n}{2}$. Thus, the maximum possible value of $m$ (the number of edges) in a simple undirected graph with $n$ vertices is $\frac{n(n-1)}{2}$. Option 2 is TRUE. **Step 3: Analyze Option 3** A graph is $k$-regular if every vertex has a degree of $k$. For a 3-regular graph, $\operatorname{deg}(v) = 3$ for all $v \in V$. Applying the Handshaking Lemma: Since every vertex has a degree of 3, the sum of degrees is $n \times 3$. Since $2m$ is an even number, $3n$ must also be an even number. For the product $3n$ to be even, and knowing that 3 is an odd number, $n$ must necessarily be an even number. Option 3 is TRUE. **Step 4: Analyze Option 4** This statement claims that if a graph has more than one vertex ($n > 1$), it must have at least one edge ($m \ge 1$). Consider a graph with $n=2$ vertices, say $V = \{v_1, v_2\}$. It is possible for this graph to have no edges, i.e., $E = \emptyset$. In this case, $m=0$. Such a graph is a simple undirected graph with $n=2$ and $m=0$. This serves as a counterexample. Therefore, the statement is not necessarily true. Option 4 is FALSE. **Answer:** The correct options are: * \boxed{The number of vertices with an odd degree is always even.} * \boxed{The maximum possible value of $m$ is $\frac{n(n-1)}{2}$.} * \boxed{If $G$ is a 3-regular graph, then $n$ must be an even number.}

**Option 1: The number of vertices with odd degrees in $G$ is always an even number.** **Step 1:** Apply the Handshaking Lemma. The Handshaking Lemma states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges: Since $2m$ is always an even number, the sum of degrees must be even. **Step 2:** Analyze the sum of degrees based on parity. Let $V_{odd}$ be the set of vertices with odd degrees and $V_{even}$ be the set of vertices with even degrees. The sum of even numbers is always even. Thus, $\sum_{v \in V_{even}} \operatorname{deg}(v)$ is even. Since $\sum_{v \in V} \operatorname{deg}(v)$ is even, it implies that $\sum_{v \in V_{odd}} \operatorname{deg}(v)$ must also be even. For a sum of odd numbers to be even, the number of terms in the sum must be even. Therefore, the number of vertices with odd degrees ($|V_{odd}|$) must be an even number. **Conclusion:** Statement 1 is necessarily true. **Option 2: If $G$ has $k$ connected components, then $m \ge n-k$.** **Step 1:** Consider the properties of connected components. Let $G_1, G_2, \dots, G_k$ be the $k$ connected components of $G$. Let $n_i$ be the number of vertices in component $G_i$ and $m_i$ be the number of edges in component $G_i$. We know that $\sum_{i=1}^k n_i = n$ and $\sum_{i=1}^k m_i = m$. **Step 2:** Apply the minimum edge property for connected graphs. For any connected graph with $n_i$ vertices, it must have at least $n_i - 1$ edges. This is because a tree on $n_i$ vertices has $n_i - 1$ edges, and a connected graph must contain a spanning tree. So, for each component $G_i$, we have $m_i \ge n_i - 1$. **Step 3:** Sum the inequalities over all components. **Conclusion:** Statement 2 is necessarily true. **Option 3: If every vertex in $G$ has degree at least 2, then $G$ must contain a cycle.** **Step 1:** Assume the contrapositive. Suppose $G$ does not contain a cycle. Then $G$ must be a forest (a collection of disjoint trees). **Step 2:** Analyze properties of trees/forests. Every tree with at least two vertices has at least two leaves (vertices of degree 1). If a component of $G$ is a single vertex ($K_1$), its degree is 0. If $n=1$, $\operatorname{deg}(v)=0$, which violates the condition $\operatorname{deg}(v) \ge 2$. If $G$ is a forest and every vertex has degree at least 2, this means no component can be $K_1$ (since $\operatorname{deg}(K_1) = 0$). Also, no component can be a tree with at least 2 vertices, because such a tree would have at least two leaves (vertices of degree 1), which contradicts the condition that every vertex has degree at least 2. **Step 3:** Conclude by contradiction. Since $G$ cannot be a forest if all vertices have degree at least 2, our initial assumption must be false. Therefore, $G$ must contain a cycle. **Conclusion:** Statement 3 is necessarily true. **Option 4: If $m > \frac{(n-1)(n-2)}{2}$, then $G$ must be connected.** **Step 1:** Determine the maximum number of edges in a disconnected graph. A simple undirected graph on $n$ vertices is disconnected if and only if it can be partitioned into at least two non-empty sets of vertices such that there are no edges between these sets. The maximum number of edges a disconnected graph on $n$ vertices can have occurs when it consists of two complete components, one being $K_{n-1}$ and the other being $K_1$ (an isolated vertex). **Step 2:** Calculate the number of edges for this maximum disconnected case. The number of edges in $K_{n-1}$ is $\binom{n-1}{2} = \frac{(n-1)(n-2)}{2}$. The number of edges in $K_1$ is $0$. So, the maximum number of edges in a disconnected graph on $n$ vertices is $\frac{(n-1)(n-2)}{2}$. **Step 3:** Apply the condition. If $G$ has $m$ edges and $m > \frac{(n-1)(n-2)}{2}$, then $G$ must have more edges than any disconnected graph on $n$ vertices can possibly have. Therefore, $G$ cannot be disconnected; it must be connected. **Conclusion:** Statement 4 is necessarily true. All four statements are necessarily true. Answer: $\boxed{\text{All four statements are necessarily true.}}$

**Step 1: Understand the graph structure and identify potential cliques.** The graph $G$ has 9 vertices, representing the squares of a $3 \times 3$ chessboard. An edge exists between two squares if a king can move between them in a single move. Let the vertices be denoted by their coordinates $(i, j)$ where $i, j \in \{1, 2, 3\}$. First, let's identify the maximum clique size ($\omega(G)$), as $\chi(G) \ge \omega(G)$. Consider the central vertex $v_{22}$