Double Eulerian Tour

Use words to describe the solution process. No programming. 4. Suppose G is a graph. We define a double Eulerian tour as a walk that crosses each edge of G twice in different directions and that starts and ends at the same vertex. Show that every connected graph has a double Eulerian tour.

Relations & Functions / Induction Proof (Discrete Mathematics)

The following commonly recognised family relationships may also be derived. For each of the following derived relationships, construct a predicate corresponding to its defining relational expression: (See attachment for full question)

less composition description

Given the relation "less" over the natural numbers N, describe the compositions as a set of the form {(x,y) | property}. less º less º less

Give an example of a binary relation R such that R is irreflexive but R^2 (R squared) is not irreflexive, and give an example of a binary relation R such that R is antisymmetric but R^2 is not antisymmetric.

For each of the following properties, find a binary relation R such that R has that property but R^2 (R squared) does not: (a) irreflexive (b) antisymmetric

Use induction to prove finite set with n elements has 2^n subsets.

Use induction to prove that a finite set with n elements has 2^n subsets.

Equivalence classes for following relation on N

5b. Describe the equivalence classes for the following relations on N. x~y iif x mod 2 = y mod 2 and x mod 4 = y mod 4

Prove that R is reflexive

8. Let R be a relation on a set S such that R is symmetric and transitive and for each x ε S there is an element y ε S such that x R y. Prove that R is an equivalence relation (i.e. prove that R is reflexive)

Analyzing Algorithm 6b

For the following algorithm find the number of times the addition operation (+) is executed during the running of the program. Answer the question by giving a formula in terms of n: for i := 1 to n do for j := 1 to i do x := x + f(x) od; x := x + g(x) od

Analzing Algorithm 8b

For the following algorithm find the number of times the assignment statement (:=) is executed during the running of the program. Answer the question by giving a formula in terms of n: i := 1; while i < n + 1 do i := i + 2; for j := 1 to i do S od od

Permutations and Combinations 8

We wish to form a committee of 7 people chosen from 5 democrats, 4 republicans, and 6 independents. The committee will contain 2 democrats, 2 republicans, and 3 independents. In how many ways can we choose the committee?