1 Show that each of the following sets is countable a set of

1) Show that each of the following sets is countable:
a) set of negative integers;
b) set of integers that are multiples of 5;

For a) and b) write the one to one correspondence between
Z+ and the specified set.

2) R is the set of real numbers. Let S = { xR | -3 < x < 0 }.
Show that the set S is not countable.

For questions 3,4 draw graphs with specified properties
or explain why no such graph exists.

3) Graph with 4 vertices of degrees 1,2,3,4.
4) Graph with 5 vertices of degrees 1,2,3,3,5.

For questions 5,6 determine which graphs are bipartite.
Redraw the ones that are bipartite graphs to show their
bipartite nature.

5)                                             6)

7) Use Dijkstra\'s algorithm to find the length of the shortest path
between vertices a and z. Show each step of the calculations.

Solution

2.

Cantor\'s diagonal is a trick to show that given any list of reals, a real can be found that is not in the list.

First a few properties:

Cantor\'s diagonal is a clever solution to finding a number which satisfies these properties. The number which is the diagonal is transformed s.t. it doesn\'t share the first digit of the first number nor the second digit with the second and so on. Thus the number is unique to the list.

This is why Cantor\'s diagonal as a method proves the result that the reals are uncountable.