Also Problem: Find an embedding for the complete bipartite graphs:
(i) K(4,4) on the torus, (ii) K(4,5) on the double torus,
and for the complete graphs,
(iii) K(6) on the torus, (iv) K(8) on the double torus.
Page 151, problems 54, 55
(A) Show the Petersen graph has a nowhere zero 5-flow.
(B) Find the error in the "proof" of the 4CT given in handouts.
(C) From handouts: pg 235 problems 16, 17, pg 245 problem 27, pg 258 problem 37
(D) Find a cycle double cover for the Petersen graph.
(i) Determine the extremal number for the star K_1,d.
(ii) Considering the results shown in class about the number of triangles
in a graph, show which result is best over the various subintervals of
values of q from (n^2)/10 up to its max value. A plot of the functions will suffice.
(iii). Determine which of the following functions is convex.
Consider the interval as ( 1, inf ).
a. f(x) = sqrt(x)
b. f(x) = x choose 2, (i.e. binomial coefficients)
c. f(x) = x ^ 2 (i.e. x squared)
d. f(x) = log x
(iv) Show that any epsilon-regular pair in G is also epsilon-regular
in the complement of G.
(v) In the definition of an epsilon-regular pair, what is the
purpose of the requirement that |X| > epsilon|A| and |Y| > epsilon|B|?