MCS-236 Homework 6

Varied due dates.

• 6#1 Due November 14, strict deadline: Come up with two possible paper topics. Identify (and, if possible, read or skim) at least one reference you can use as a starting point for your preferred topic. Come to class with a paragraph describing the topic and describing your hopes for finding research references to help you with your topic.

• 6#2 Due November 19: (West 3.1.1 on page 118)

• 6#3 Due November 21: (West 3.1.4 on page 118) I'll start off by doing the second one. I'll show that if the maximum matching is of size 1, the graph is either a star or a triangle, with potentially some isolated vertices.

  If the maximum sized of a matching is 1, every pair of edges in G must share a vertex in common. If every pair shares the same vertex, then G is a star. Suppose, on the other hand, there are three edges, say e₁, e₂, and e₃ such that e₁ and e₂ meet at a vertex different from the vertex that e₂ and e₃ meet at. Since G is simple, e₁ and e₃ must share yet a third vertex, and we have a triangle. Furthermore, if any other edge is incident to any of the three vertices of the triangle, then that edge would be part of a matching with the opposite edge in the triangle.

• 6#4 Due November 22: (West 3.1.19)

  As an example, the sets {a,c}, {a,d}, {d,e}, and {a,b,d} has the SDR {a,d,e,b}, since the four elements are distinct and a is in {a,c}, d is in {a,d}, e is in {d,e} and b is in {a,b,d}.

  On the other hand, A = {a,b}, B = {b,c,d,f}, C = {a,e}, D = {b,e}, and E = {a,b,e} don't because the union of the four sets A,C,D and E is {a,b,e} which has only three elements.