I took it yesterday and it was pretty insane. Pretty much the same format as the midterm 10 questions, do 4 of the first 7 and 2 of the last 3. The first problem was a joke…pretty much a straight forward application of the principle of inclusion-exclusion. I goofed around with the second problem a little, but part B asked if 2 graphs were isomorphic or not…I was pretty certain they were, but I wasn’t able to find an isomorphism so I ended up skipping the problem.
The second problem I did was pretty easy as well. There was some parts about an equivalence relation and then a proof, given G a graph and H and K connected subgraphs of G with a non-null intersection show that the union of H and K was connected. Turns out that wasn’t that difficult of a problem.
The third problem I did wasn’t really difficult, but it was time consuming. The first 2 parts were to define what a tree was and give a general method for constructing a spanning tree of a connected graph. The third part gave 3 trees with 6 edges and asked to find all trees, up to an isomorphism, with 7 edges containing the given trees. That wasn’t hard, but then the part about showing that there were no duplicates took about a page of work to get through.
The fourth problem I did was where things started to go downhill. Part A asked whether or not the graph of knight moves on a 5×5 chessboard had a Hamiltonian cycle, this wasn’t hard since I had messed around with the 5×5 board previously and had a pretty good pretty good argument for why any Hamiltonian path of such a graph could be assumed to start at the bottom left corner of the board. Part B was again pretty easy in that it only asked if the Peterson graph had a Hamiltonian cycle, so proof by example was a pretty much all that was necessary. Part C however was to so that the graph of a D dimensional cube had a Hamiltonian cycle; I got a proof of sorts using inductive reasoning, but well it was mostly a bunch of hand waving.
The fifth problem again was a trouble spot…it was inclusion-exclusion again, but I kept messing up the counting. I left some work on there, but never got a solution of any sort. I pretty much felt like I had to work on that problem since the problem I skipped was to prove 1 of 3 theorems: Hall’s theorem, Delwar’s theorem, or inclusion-exclusion. I probably could have wrote something for a couple of these, but honestly in the in it would probably be mostly just hand-waving…plus I ran out of time.
The last problem was to just provide definitions. I think I did alright on this one, except my definition of a set family didn’t really seem like it was what he was looking for, but well I couldn’t really think of any other way to define it.