Discrete Mathematical Structure and Graph Theory - B.Tech 4th Semester Exam., 2018

For any three sets A, B and C, which of the following statements is wrong?

1. \( A \cup (B \cup C) = (A \cup B) \cap C \)
2. \( A \cup (B \cup C) = A \cup (B \cup C) \)
3. \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \)
4. None of the above

Let A and B be two non-empty sets. Then the set of all ordered pairs (a, b), where \( a \in A \) and \( b \in B \) is called

1. product set
2. poset
3. binary set
4. None of the above

If \( (a,a) \in R \) or equivalently \( a R a \), \( \forall a \in A \), then a relation R on a set A is called

1. equivalent
2. reflexive
3. symmetric
4. anti-symmetric

Let A and B be finite sets with \( |A| = n \) and \( |B| = m \). How many functions are possible from A to B with A as the domain?

1. n
2. \( m^m \)
3. m
4. \( m^n \)

For the functions f and g defined by \( f(x) = x^3 \) and \( g(x) = x^2 + 1 \; \forall x \in R \), the value of \( (g \circ f)(x) \) is

1. \( x^2 + 1 \)
2. \( x^3 + 1 \)
3. \( x^6 + 1 \)
4. \( x^5 + 1 \)

A group G is said to be Abelian (or commutative) if for every

1. \( a, b \in G \)
2. \( a \cdot b = b \cdot a \)
3. Both (i) and (ii)
4. None of the above

If \( f : G \rightarrow G' \) is a homomorphism, then which of the following it true?

1. \( f(e) = e \)
2. \( f(e) = e' \)
3. \( f(e) >= \Phi \)
4. \( f(e) = 1 \)

For which of the following does there exist a tree satisfying the specified constraints?

1. A full binary tree with 31 leaves, each leaf of height 5
2. A rooted tree of height 3 where every vertex has atmost 3 children and there are 41 total vertices
3. A full binary tree with 11 vertices and height 6
4. A binary tree with 2 leaves and height 100

For which of the following does there exist a graph \( G(V, E) \) satisfying the specified conditions?

1. A tree with 9 vertices and the sum of the degrees of all the vertices is 18
2. A graph with 5 components, 12 vertices and 7 edges
3. A graph with 5 components, 30 vertices and 24 edges
4. A graph with 9 vertices, 9 edges and no cycles

The number of simple digraphs with \( |V| = 3 \) is

1. \( 2^9 \)
2. \( 2^8 \)
3. \( 2^7 \)
4. \( 2^6 \)

Let \( f(x) = ax^2 + b \) and \( g(x) = cx^2 + d \), where a, b, c and d are constants. Determine for which constants a, b, c and d the following equation holds: \( f \circ g = g \circ f \)

Show that the relation \( (x, y) R (a, b) \) such that \( x^2 + y^2 = a^2 + b^2 \) is an equivalence relation on the plane and describe the equivalence classes.

Let \( (G, \cdot) \) be a group, where \( \cdot \) is usual multiplication operation on G. Then show that for any \( x, y \in G \) following equations hold:
(i) \( (x^{-1})^{-1} = x \)
(ii) \( (xy)^{-1} = y^{-1}x^{-1} \)

Construct the truth table for \( [(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)] \rightarrow r \). Also show that above statement is a tautology by developing a series of logical equivalences.

If \( A = \{1, 2, 4\} \), \( B = \{2, 5, 7\} \) and \( C = \{1, 3, 7\} \), find \( (A \times B) \cup (A \times C) \).

List the ordered pairs in the relation R from \( A = \{1, 2, 3, 4\} \) to \( B = \{2, 3, 4, 5\} \), where \( (a, b) \in R \) if and only if-
(i) \( a = b \)
(ii) \( a + b = 5 \)

Show that the set of integers with the composition \( \circ \) and * defined by \( a \circ b = a + b + 1 \) and \( a * b = ab + a + b \) is a ring.

State and prove Lagrange's theorem.

Define a relation R on the set Z of all integers as follows: \( m R n \Leftrightarrow m+n \) is even for all \( m, n \in Z \). Is R a partial order relation? Prove or give a counter example.

Show that the group
(i) \( \{1, 2, 3, 4\}, X_5 \)
(ii) \( \{1, 2, 3, 4, 5, 6\}, X_7 \)
is cyclic.

Let \( A = \{0, 1, 2, 3\} \), \( R = \{(x, y) : x+y=3\} \), \( S = \{(x, y) : 3|(x+y)\} \), \( T = \{(x, y) : \max(x,y)=3\} \). Compute (i) \( R \circ T \), (ii) \( T \circ R \) and (iii) \( S \circ S \).

In a group of 70 cars tested by a garage in Delhi, 15 had faulty tyres, 20 had faulty breaks and 18 exceeded the allowable emission limits. Also, 5 cars had faulty tyres and brakes, 6 failed on tyres and emission, 10 failed on brakes and emissions, and 4 cars were unsatisfactory in all three respects. How many cars had no faults in these three checks? Draw an appropriate Venn diagram.

Define the vertex connectivity and edge connectivity of a graph. Prove that for a graph G with n vertices and e edges, vertex connectivity \( \le \) edge connectivity \( \le 2e/n \).

Define the adjacency matrix of a graph. Find the rank of the regular graph with n vertices and with degree \( p (< n) \) of every vertex.

• Multigraphs
• Planar graphs
• Cosets
• Ring polynomials