Description

CS 70 Discrete Mathematics and Probability Theory

1 Graph Isomorphic
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and
H
f :V(G)→V(H)
such that any two vertices u,v of G are adjacent in G if and only if f(u), f(v) are adjacent in H.
Prove the following:
1. The degrees of corresponding nodes u, f(u) are the same.
2. There is a bijection between edges.
3. If G is connected, then H is also connected.
2 Countability Practice
(a) Do (0,1) and R+ =(0,∞) have the same cardinality? If so, either give an explicit bijection (and prove that it is a bijection) or provide an injection from (0,1) to (0,∞) and an injection from (0,∞) to (0,1) (so that by Cantor-Bernstein theorem the two sets will have the same cardinality). If not, then prove that they have different cardinalities.
(c) Consider the previous part, except now the strings are drawn from a countably infinite alphabet A . Does your answer from before change? Make sure to justify your answer.
3 Python Functions
(a) The set F ={f : N→{0,1}} is not countable.
(b) Prove that the set of all python functions that output {0,1} is countable. (Python functions have the same power as Turing machines, but people are more familiar with python.)
(c) The set of Python functions that take in input x and output either 0 or 1 appears to be the same as F in (a), but the set of Python function is countable. Why?