Problem Set 1

This problem set does not contribute to your final course grade, but is useful practice writing proofs for the exam. It is due in class on Friday, March 3rd.

Question 1

Find a Hamiltonian cycle in the following graph:

Question 2

Prove that the following graph is not Hamiltonian:

Question 3

We saw in class that $\Gamma$ has a vertex such that removing it disconnects the graph, then $\Gamma$ is not Hamiltonian. Prove the following generalization:

Suppose that graph $\Gamma$ has $n$ vertices $v_1,\dots, v_n$ so that if we remove all $n$ vertices, the resulting graph $\Gamma\setminus \{v_1,\dots, v_n\}$ has more than $n$ components. Prove that $\Gamma$ is not Hamiltonian.