CSC 280 Problem Set 1: Proofs

Work on these problems, and bring your solutions to the Wednesday workshop. You will discuss but not turn in your solution. The weekly quiz problems will use concepts and methods used in these problems.

1. Prove by contradiction that square root of 3 is irrational.

2. Textbook problem 0.10. What kind of proof does this attempt to be?

3. Prove by induction that for n >= 4, the following inequality holds: 2^n < n!

Notation: 2^n means 2 to the power n. n! means n factorial.

4. A bipartite graph is one whose nodes can be separated into two non-empty sets U and V, such that every edge connects a node in U with one in V.  Prove by construction that any tree T is bipartite.

5. Now, prove that any graph that does not contain an odd cycle is bipartite.

6. Prove by contraction that every graph with 2 or more nodes contains two nodes that have equal degrees.