my email: yashasavelyev@gmail.com

HW Set 1 (Using book Walk in combinatorics) for wed

1. Show that both weak and strong induction in the book, are consequences of our induction principle from class. (Hing: Use the trick of constructing a stronger sentence) pg 10: 1,2,3,4,5
   pg 31: 1,2,3,4,9
   Set 3: from Wilson graph theory

Set 2 (Using book: Introduction to graph theory, Wilson, 4th edition) 1: Construct graphs G₁, G₂ 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 v_i, v_i − 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,

1. Find the Euler characteristic of a surface of genus 2 from which n disks have been cut out.

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 ∈ IU_i, I countable, of countable sets U_i 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

–> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –> –>