Discrete Mathematics Answers

given: f(n) = 3f(n/2) + 5n^3 where n=2k and f(1) = 2
find f(n) and a big -0 estimate of f(n)

Find a counter example to the following universally quantified statements, where the domain for all variables consist of all integers. ∀x, x^2, <=x^3.

Width of a tree is defined as the largest distance(number of edges in the shortest path) between any two vertices. What is the smallest possible width of the tree with 100 vertices?

1


2


99


101
1 point
How many complete graphs with at least 1 edge and at most 50 edges are there?

8


9


10


11

Q.Which of the following can be a degree sequence of a simple graph?

{4,4,3,2,1}


{4,3,2,1}


{4,4,3,2}


{4,2,2,2,2}

Q.If G is a connected simple graph and e,f and g are edges of G, then which of the following is/are true:

There is always a spanning tree of G that contains e


There is always a spanning tree of G that contains e and f


There is always a spanning tree of G that contains e,f and g


All of the above.
Q.If G is a simple, disconnected graph on n vertices, how many maximum edges can it have?

n−2


(n2)


(n−12)


(n−12)+1
Q.Which of the following statements is NOT true?

The maximum number of cut vertices in any simple, connected graph on n vertices is n−2


If there exist a cut-edge in the graph, then a cut-vertex must also exist.


If there exist a cut-vertex in the graph, then a cut-edge must also exist.


The maximum number of cut-edges in any simple graph on n vertices is n−1.

Which is the following statements is True?

Every path is a trail but every walk is not a trail


Every walk is a trail but every path is not a trail.


Both paths and walks are trails.


Neither a path nor a walk is a trail
1 point
Let G be a graph on 9 vertices such that the sum of the degrees is at least 27. Then G must have a vertex of degree at least

4


5


6


7
1 point
Which of the following statements is false?

Number of people currently living on our planet and having odd number of siblings is even


For a k-regular graph, if k is odd, then number of vertices in the graph must be even


In any simple graph there are two vertices with the same degree


{3,2,1,0} can be a degree sequence of a simple graph on 4 vertices

How many bit strings can be formed by using seven 1s and nine 0s?

Compute the number of distinct arrangements of the characters ABBCCCDDDDEEEEE

How many solutions are there to the equation x1+x2+x3+x4+x5+x6= 25 where the xi(for i= 1,2,3,4,5,6) are non-negative integers?

Let S={a, b, c, d, e}. Find the number of ways to select 7 elements from S when repetition is allowed. The order in which the elements are chosen does not matter

Use Mathematical Induction to prove the Binomial Theorem.