Discrete Mathematics - B.Tech 4th Semester Exam., 2022 (New Course)

The statement \( (\sim P \leftrightarrow Q) \wedge \sim Q \) is true, when

1. P: True, Q: False
2. P: True, Q: True
3. P: False, Q: True
4. P: False, Q: False

Which of the following statements regarding sets is false?

1. \( A \cap A = A \)
2. \( A \cup A = A \)
3. \( A - (B \cap C) = (A - B) \cup (A - C) \)
4. \( (A \cup B)' = A' \cup B' \)

What is the induction hypothesis assumption for the inequality \( m! > 2^m \) where \( m \ge 4 \)?

1. For \( m = k \), \( (k+1)! > 2^k \) holds
2. For \( m = k \), \( k! > 2^k \) holds
3. For \( m = k \), \( k! > 3^k \) holds
4. For \( m = k \), \( k! > 2^{k+1} \) holds

A simple graph can have

1. multiple edges
2. self-loops
3. parallel edges
4. no multiple edges, self-loops and parallel edges

An undirected graph has 8 vertices labelled 1, 2, ..., 8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?

1. 15
2. 8
3. 5
4. 23

A graph which has the same number of edges as its complement must have number of vertices congruent to ___ or ___ modulo 4 (for integral values of number of edges).

1. \( 6k, 6k-1 \)
2. \( 4k, 4k+1 \)
3. \( k, k+2 \)
4. \( 2k+1, k \)

A graph which consists of disjoint union of trees is called

1. bipartite graph
2. forest
3. caterpillar tree
4. labelled tree

Which of the following two sets are equal?

1. \( A = \{1, 2\} \) and \( B = \{1\} \)
2. \( A = \{1, 2\} \) and \( B = \{1, 2, 3\} \)
3. \( A = \{1, 2, 3\} \) and \( B = \{2, 1, 3\} \)
4. \( A = \{1, 2, 4\} \) and \( B = \{1, 2, 3\} \)

If \( C_n \) is the nth cyclic graph, where \( n > 3 \) and n is odd, determine the value of \( X(C_n) \)

1. 32572
2. 16631
3. 3
4. 310

The number of edges in a regular graph of degree 46 and 8 vertices is

1. 347
2. 230
3. 184
4. 186

Let \( D = \{-48, -14, -8, 0, 1, 3, 16, 23, 26, 32, 36\} \). Determine which of the following statements are true and which are false. Provide counterexamples for those statements that are false.
(i) \( \forall x \in D \), if x is odd, then \( x > 0 \)
(ii) \( \forall x \in D \), if x is less than 0, then x is even
(iii) \( \forall x \in D \), if x is even, then \( x \le 0 \)

Indicate which of the following statements are true and which are false. Justify your answers as best you can:
(i) \( \forall x \in Z^+ \), \( \exists y \in Z^+ \) such that \( x = y + 1 \)
(ii) \( \forall x \in Z \), \( \exists y \in Z \) such that \( x = y + 1 \)
(iii) \( \exists x \in R \) such that \( \forall y \in R \), \( x = y + 1 \)
(iv) \( \forall x \in R^+ \), \( \exists y \in R^+ \) such that \( xy = 1 \)
(v) \( \forall x \in R \), \( \exists y \in R \) such that \( xy = 1 \)
(vi) \( \forall x \in Z^+ \) and \( \forall y \in Z^+ \) \( \exists z \in Z^+ \) such that \( z = x - y \)
(vii) \( \forall x \in Z \) and \( \forall y \in Z \), \( \exists z \in Z \) such that \( z = x - y \)
(viii) \( \exists u \in R^+ \) such that \( \forall v \in R^+ \), \( uv < v \)

Prove the following:
(i) There is a real number x such that \( x > 1 \) and \( 2^x > x^{10} \).
(ii) There is an integer n such that \( 2n^2 - 5n + 2 \) is prime.

Disprove that for all real numbers a and b, if \( a < b \), then \( a^2 < b^2 \).

Show that \( p \vee (q \wedge r) \) and \( (p \vee q) \wedge (p \vee r) \) are logically equivalent. This is the distributive law of disjunction over conjunction.

Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.

If a and b are positive integers, then prove that there exists integers s and t such that \( gcd(a,b) = sa + tb \).

Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term a and common ratio r:
\( \sum_{j=0}^{n} ar^j = a + ar + ar^2 + \cdots + ar^n = \frac{ar^{n+1}-a}{r-1} \) when \( r \ne 1 \), where n is a non-negative integer.

Write short notes on the following:
(i) Forward proof
(ii) Disjunctive and conjunctive normal form
(iii) Fundamental theorem of arithmetic

An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie.

Prove Bernoulli's inequality that if \( h > -1 \), then \( 1 + nh \le (1 + h)^n \) for all non-negative integers n.

What is pigeonhole principle? Using it, prove the following:
During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

What is pigeonhole principle? Using it, prove the following:
The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that \( 10 = 3^2 + 1 \). There are four strictly increasing subsequences of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; and 1, 4, 5, 7. There is also a strictly decreasing subsequence of length four, namely, 11, 9, 6, 5.

In a Round-Robin tournament, the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles and the Cardinals beat the Orioles. Model this outcome with a directed graph.

Let \( G=(V,E) \) be a simple graph. Let R be the relation on V consisting of pairs of vertices (u, v) such that there is a path from u to v or such that \( u = v \). Show that R is an equivalence relation.

Determine whether the following given pair of directed graphs, shown in Fig. 1 and Fig. 2, are isomorphic or not. Exhibit an isomorphism or provide a rigorous argument that none exists.

Use pseudocode to describe an algorithm for determining the value of a game tree when both players follow a minmax strategy.

Suppose that \( T_1 \) and \( T_2 \) are spanning trees of a simple graph G. Moreover, suppose that \( e_1 \) is an edge in \( T_1 \) that is not in \( T_2 \). Show that there is an edge \( e_2 \) in \( T_2 \) that is not in \( T_1 \) such that \( T_1 \) remains a spanning tree if \( e_1 \) is removed from it and \( e_2 \) is added to it, and \( T_2 \) remains a spanning tree if \( e_2 \) is removed from it and \( e_1 \) is added to it.

Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamiltonian path in the graph.