Discrete Mathematics Answers

A plane sheet of material is bound by the curve y = x^2 from x = 0 to x =1, the x-axis
and the line x =1. If the mass per unit area (density) of the sheet is xy find the mass of
the sheet.

How many edges does a complete tournament graph with n vertices have?

a) n(n-1)/2
b) n-1
c) n
d) none of the above.

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then size of the maximum independent set of G is

a) more than 12
b) less than 8
c) 8
d) 12

What is the number of perfect matching of a complete graph Kn with n vertices?

Consider the following two problems on undirected graphs:
α: Given G(V,E), does G have an independent set of size |v|—4?
β: Given G(V,E), does G have an independent set of size 5?
Which one of the following is TRUE?

a) α is in P and β is NP-complete
b) α is NP complete and β is in P
c) Both α and β are NP-complete
d) Both α and β are in P

What is the number of elements in the smallest equivalence relation over set A with |A|=n ?

Let S be a set of n elements. The number of ordered pairs in the largest and the
smallest equivalence relations on S are:
(A) n and n (B) n^2 and n (C) n^2 and 0 (D) n and 1

What is the number of perfect matchings of K6? Explain.

A graph G and its complement G have 8 and 7 edges respectively. What is the
number of vertices in G ?

Find the transitive closure of R = {(a, a), (b, a), (b, c), (c, a), (c, c), (c, d), (d, a), (d, c)} on the set {a, b, c, d}.