Relations and Graph Theory.

1. List all the functions from the three element set {1, 2, 3} to the set {a, b}. Which functions, if any, are one-to-one? Which functions, if any, are onto?
2. How many base 10 numbers have 3 digits? How many three-digits numbers have no two consecutive digits equal? How many have at least one pair of consecutive digits equal?
3. Suppose you are choosing participants for a panel discussion on allowing alcohol in campus. You must choose four administrators from a group of 10 and four students from a group of 20. In how many ways can this be done?
4. Define a binary relation S from R to R as follows: for all (x, y)  R x R, x S y  x |y.
a) Is (2, 4)  S? Is (4, 2)  S? Is (2, 2) S? Is (-2) S (-8).
b) Find the set of all elements u with the property that (2, u)  S.
c) Find the set of all elements v with the property that (1, v)  S.
5. In how many ways can you pass out k identical apples to n children if each child must get at least one apple?
6. Write a negation, the contrapositive, the converse and inverse for the following statement:
If n is divisible by 6, then n is divisible by 2 and n is divisible by 3.
7. Determine if the statements (r  p)  ((~ r  (p  q))  ( r  q) and p  q are logically equivalent. Justify your answer using truth table below (You may not need to use all of the columns in the skeleton table.)

p q r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F

8. Use truth tables to show that the following forms of argument are invalid:
a) The statements (p q) and q are both true, thus, it follows p is true as well (converse error).
b) The statements (p q) and (~p) are both true, thus, it follows ~q is true as well (inverse error).
9. Rewrite the statement The product of odd integers is odd. with all quantifiers (including any in the definition of odd integers) explicitly stated as "for all" or "there exist."
10. Prove that for any integers m and n, if m is odd and n is odd, then mn is odd.
11. Prove by induction that for all integers 13 + 23 + 33 + ... + n3 = n2(n+1)2/4
12. When paying off a loan with initial amount A and monthly payment M at an interest rate of p percent, the total amount T(n) of the loan after n months is computed by adding p/12 percent to the amount due after n-1 months and then subtracting the monthly payment M. Convert the description into a recurrence for the amount owed after n months. Solve the recurrence derived.
13. Are there graphs with v vertices and v-1 edges that are no trees? Give a proof or justify your answer with a counterexample.
14. The diagram below is a rooted tree; the root is indicated.
a) What is the level of the vertex indicated by the circle?
b) What is the height of the tree?

15. Draw a binary tree, height 4, with 17 terminal vertices or explain why no such a tree exists.
16. How many vertices does a complete binary tree of height n have? Prove it. Hint: Starting from height 1, 2, and 3, derive a relation (h(n)) of the height (h) depending on the number of nodes (n) and prove it by induction.
17. How many Binary Search Trees can be constructed given 3 keys (say 1, 2 and 3)? Draw them (or explain the parent-child relationship for each; or provide the preorder traversal for each).
 
18. Given the graph:

a) Which vertices are adjacent to vertex G?
b) Which edges are adjacent to EG?
c) Is there any Eulerian circuit in the graph? Find one or explain why not.
d) List 3 loops that start at A.
e) Find a spanning tree starting at node A
19. Find all minimal spanning trees of the graph below.

20. For the graph below, find:
a. An elementary path;
b. A simple path;
c. A path which is not simple;
d. A simple path which is not elementary;
e. A simple circuit;
f. A circuit which is not simple.

21. For the graph below, find if it has an Eulerian circuit. If not, explain why. If yes, find one.