Happy Chanukah
by yugrey, Dec 22, 2014, 2:52 PM
Before the holiday ends, I would like to wish the blog owner a very happy Chanukah.
Also to any Christians reading this blog, Merry Christmas.
And to everyone, Happy New Year.
Happy Holidays. Here is Tuymaada 2008 #5 (senior) from http://www.artofproblemsolving.com/Forum/resources.php?c=1&cid=98&year=2008.
Solution
Also to any Christians reading this blog, Merry Christmas.
And to everyone, Happy New Year.
Happy Holidays. Here is Tuymaada 2008 #5 (senior) from http://www.artofproblemsolving.com/Forum/resources.php?c=1&cid=98&year=2008.
Solution
We have a connected graph
such that the removal of any path or cycle keeps the graph connected. Prove the graph has a Hamiltonian cycle.
This is rather easy, assuming I am correctly interpreting the statement. take the maximal cycle
and remove it assuming it is not Hamiltonian. Now, note that
connects to some
and
connects to some
. If
, then
is a bigger cycle, oops. Else there is a path
,...
where
are distinct from
and we have that
is a bigger cycle. Contradiction.

This is rather easy, assuming I am correctly interpreting the statement. take the maximal cycle











