Directed Graphs and Trees

a. Is a directed graph weakly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph? b. If two trees have the same number of vertices and the same degrees, are the two trees isomorphic?

Trees

a. If T is a rooted binary tree of height 5, then T has at most 25 leaves. b. If T is a tree with 50 vertices, the largest degree that any vertex can have is 49.

Inorder Traversal and Hamilton Path

Please see the attached file for the fully formatted problems. Also, can a tree have a Hamilton path?

Trees : Rooted Binary Path and Hamilton Path

I need to know if these are true, and if so why. a.)In a rooted binary tree with 16 vertices, there must be a path of length 4. b.)No tree has a Hamilton path.

Prove the Transitive Theory

Prove the following theory: 1) R1 is a subset of R2 => All of R3, R1R3 is a subset of R2R3 and 2) R1 is a subset of R2 => All of n, (R1)^n is a subset (R2)^n 3) Suppose R is transitive, then for all of n, R^n is a subset of R.

Partitions on a Set

We denote the number of partitions of a set of n elements by P(n). Suppose the number of partitions of a set on n elements into k parts is denoted by P(n,k). Then obviously P(n) = P(n,1) + P(n,2) + ….. + P(n,n) Show that P(n,2) = 2^(n-1) - 1

Prove that there is no bijection between any set A and its power set P(A) of A.

There is no bijection between any set A and its power set P(A) of A. For finite sets, proof is trivial since |A| = n and |P(A)| = 2^n. For finite sets, this is done by contradiction. Suppose there is a bijection $ between a set A and its power set P(A). Consider the set B={x|x is a member A where x is not a member $(x)}For e ...continues

Discrete Math : N multichoose K Proof

Please see the attached file for the full problem description. The double bracket notation is pronounced " n multichoose k". The doubled parentheses remind us that we may include elements more than once.

Discrete.

Please see the attached file for full problem description.

Rabbit Farm

You own a rabbit far. Every week each pair of rabbits has two baby rabbits. However, the baby rabbits first reproduce when they are two weeks old. Initially you have a pair of newborn rabbits. How many pairs you have after n weeks?