Problem Set 10

Most of the problems are assigned from the required textbook Amazon logo Bona, Miklos. A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing Company, 2011. ISBN: 9789814335232. [Preview with Google Books]

A problem marked by * is difficult; it is not necessary to solve such a problem to do well in the course.

Problem Set 10

  • Due in Session 30
  • Practice Problems
    • Session 25: Chapter 10: Exercise 17
    • Session 26: Chapter 11: Exercise 3
    • Session 27: Chapter 11: Exercise 3
    • Session 28: Chapter 11: Exercises 4, 9, 12, 15, 16
  • Problems Assigned in the Textbook
    • Do problems 1 and 2 from the Matrix-Tree Theorem (PDF). Problem 2 deserves a star (*). For this problem, you will need the concept of the dual of a planar graph, defined in Definition 12.12, pp. 282, of the text. The first step is to prove that if G is a planar graph, then κ(G) = κ(G*). If you are unable to show that κ(G) = κ(G)*, you should just assume it and continue with the problem.
    • Chapter 11: Exercise 26. 26(a) is pretty easy, but 26(b) is difficult.
  • Additional Problems
    • (A14*) Let Gn denote the complete graph K2n with n vertex-disjoint edges (i.e., a complete matching) removed. Use the Matrix-Tree theorem to find κ(Gn), the number of spanning trees of Gn. (This is not so easy. Find the eigenvalues of the Laplacian matrix L of G. Several tricks are needed.)
    • (A15) Let m and n be two positive integers. Find the number of Hamiltonian cycles of the complete bipartite graph Km,n. (There will be two completely different cases.)
    • (A16) (a) Let G be the infinite graph whose vertices are the points (i,j) in the plane with integer coordinates, and with an edge between two vertices if the distance between them is one. Is G bipartite? (b*) What if the vertices are the same as (a), but now there is an edge between two vertices if the distance between them is an odd integer?
  • Bonus Problems
    • None