Second Midterm Study Questions
Exam on Friday February 23

The test will be closed book and closed notes, individual work only.

Unless otherwise directed, you must show your work. It is to your advantage to show your work even when not required to do so, since partial credit may be awarded for those portions of the work that are correct.

Should the weather turn inclement, the exam will still be held, unless the University is closed for the day.

Study Questions

• For what values of j and k is there a connected graph with
  • j vertices of degree 1
  • k vertices of degree 2
  • one vertex of degree 3
• Find two graphs with the same degree sequence such that one is planar and one is not.
• Give an example of a binary relation R on set A and a property, P, such that there is no P-closure of R.
• Graph G is connected and planar and has at least one region of degree 10
  • What is the least number of vertices G might nave?
  • Given that G has k vertices, find an upper bound on the number of edges in G.
• Notation is a little wierd on this one. I'm using J[k](R,S) as if k were a subscript of J, and similarly with P[i,j,k](R,S).

  Let R be an m-ary relation having j rows and field m a primary key.
  Let S be an n-ary relation having k rows and field 1 a primary key.

  • What is the minimum number of rows in J[1](R,S)?
  • What is the maximum number of rows in J[1](R,S)?
  • Is it true that P[1,m+n-1](J[1](R,S)) = P[1,3](J[1](P[1,m](R),P[1,n](S)))?
    Either prove it is true or find a counterexample.