Discrete Mathematics — Winter 2025

Draw the graph with 4 nodes and 7 edges.

Define simple graph, degree of a vertex, finite and infinite graphs and complete graph.

(i) If A = B = {1, 2, 3, 5, 6, 10, 15, 30} and relation Rdefined as a/b, where a∈Aand b∈B. Find the relation matrix. (ii) Solve the recurrence relation a - 3a = 2, n ≥ 1, a = 1. n n-1 0

Let A, Band Cbe the sets such that (A∩B∩C) = ∅, (A∩B) ≠ ∅, (A∩C) ≠ ∅, (B∩C) ≠ ∅. Draw the corresponding venn diagram.

Define subgroup of a group. Also, show that the subset Hof a group of integers Iis a subgroup under addition, where H = {...., -2m, -m, 0, m, 2m, .....}.

How many integers between 1 to 2000 are divisible by 2, 3, 5 or 7.

Using venn diagram, prove the following

A∪(B∩C) = (A∪B)∩(A∪C) (ii) A⊕(B⊕C) = (A⊕B)⊕C

Check whether the proposition ((pνq)Λ∼p)→q is contradiction, tautology or contingency.

Show that the proposition (p→(q→r))→((p→q)→(p→r)) is a tautology.

Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 18, 24} be ordered by the relation x divides y. Show that the relation is partial ordering and draw the Hasse diagram.

Show that the propositions p→q and ∼pvq are logically equivalent.

Negate (opposite) each of the following statements

∀ x, |x| = x (ii) ∃ x, x2 = x (iii) If there is a riot, then someone killed. (iv) It is day light and all the people are arisen. Page 1 of

Solve the following recurrence relation

Explain Partially order relation, Poset and Hasse diagram with example(s)

Explain the regular graph and complete bipartite graph with example(s).

Define tree and root. Also draw a tree with 10 vertices which has vertices either of degree 1 or of degree 3. Is it possible to draw a same type of tree with 11 vertices?

Let n be a positive integer, Sbe the set of all divisors of n. Let Ddenote the relation n of division. Draw the lattices for (i) n = 24, (ii) n = 30

Draw the following grapghs

K (ii) K (iii) K (iv) K 3, 4 4, 4 5, 4

Find minimum spanning tree for the weighted graph given below

Define abelian group for any non empty set.

If G = {0, 1, 2, 3, 4, 5, 6, 7} and operation + is an addition modulo 8, then show that8 (G, + ) is an abelian group.8

Consider the set (C, +, . ), where Cis the set of complex numbers and + and . are ordinary addition and multiplication operation. Show that (C, +, . ) is a field.

Let Qbe the set of all positive rational numbers and ∗ be a binary operation on Q + + defined by a∗b = ab/3 , then show that (Q ∗)is an abelian group. +,

Define cyclic group and show that the following groups are cyclic groups

Third roots of unity i.e. G = {1, ω, ω2}, ω3 = (ii) G = {1, -1, i, -i}, where i2 = -1

Show that R = {a+b√2; a, b ∈ I} is an integral domain but not a field under the binary operations + (usual addition) and . (usual multiplication). Page 2 of