my email: yashasavelyev@gmail.com
HW Set 1 (Using book Walk in combinatorics) for wed
Set 2 (Using book: Introduction to graph theory, Wilson, 4th edition)
1: Construct graphs G1, G2 with same number of
edges and vertices, which are NOT isomorphic.
5.1, 5.3, 5.4
6.1, 6.2
7.1, 7.2
Set 3 (Wilson)
Extra credit: 1) Complete proof of Theorem 7.1 by proving that vertices vi, vi − 1 exist. Hint: this can be proved by induction on n. Extra credit: 2) Prove that a graph with n vertices and n − 2 edges is disconnected.
8.4, 9.3, 9.6, 9.10
set 4, Wilson
12.1, 12.3, 12.7, 13.2, 13.5
set 5,
Wilson: 15.1, 15.2, 15.3, 15.5
Set 6:
1: Let S be an infinite subset of a countable set F, prove that S is countable. (Hint: You should be able construct the needed isomorphism directly.)
2: Prove that ℤ is countable.
4: Prove that a countable union ∪i ∈ IUi, I countable, of countable sets Ui is countable.
5: Extra credit: Prove that ℝ is uncountable, using the diagonalization argument we studied in class.
Set 7:
Hopfcroft: 2.2.1, 2.2.2, 2.2.9, 2.3.4
Set 8:
Hopfcroft: 8.2.2
–> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –>