UMBC CMSC203 Discrete Structures, Section 06, Spring 2016

Homework 2, Due Thursday, 02/11

1. Vertex Cover. Consider a graph G. Let X be a subset of the vertices in G. We say that X is a vertex cover of G if for every edge in G at least one of the endpoints of that edge is in X.

   In the graph below, find a vertex cover with as few vertices as you can. List the vertices of the vertex cover you found and briefly argue that it is the smallest possible.

   Hint: the smallest vertex cover in this graph has 10 vertices.

   

2. Hamiltonian Circuits. [Adapted from Problem Solving Through Recreational Mathematics by Averbach & Chein, 1980.]
   A graph has a Hamiltonian circuit if there is a path in the graph that visits every vertex exactly once and returns to the first vertex in the path.
   1. Does the graph below have a Hamiltonian circuit? Justify your answer.

      

   2. In general, if a graph has a Hamiltonian circuit, is it necessarily the case that the graph has an Euler circuit? Justify your answer.
   3. In general, if a graph has an Euler circuit, is it necessarily the case that the graph has a Hamiltonian circuit? Justify your answer.

3. Regular Graphs. In a d-regular graph, every vertex in the graph has degree d. Recall that the degree of a vertex is the number of edges incident on the vertex. (I.e., count the number of edges coming out of a vertex and that is its degree.)
   1. Draw a 3-regular graph with 6 vertices.
   2. Draw a 3-regular graph with 8 vertices.
   3. Draw a 3-regular graph with 10 vertices.
   4. Are there any 3-regular graphs with 9 vertices? why or why not?