(a)
(x+y+v1)(~z+v2+~v1)(w+v3+~v2)(u+~v+v3)(~x+~y+v4)(z+v5+~v4)(~w+v6+~v5)(u+v+~v6)
(x+~y+v7)(~z+v8+~v7)(w+v9+~v8)(w+v9+~v8)(u+~v+~v9)(x+y+v10)(x+y+~v10)

(b)

(c)

6.1   The general vertex cover problem is known to be NP complete. 
The graph obtained by reduction from the 3-SAT problem may be converted into an 
even degree graph by adding a new edge between any two vertices if the original 
graph contained an edge between these two vertices. Now if a vertex cover is found
 in this multigraph in polynomial time then a vertex cover in the general graph 
may also be found in polynomial time, which is impossible. Hence proved.


6.2 The vertex cover problem is known to be NP complete. So we'll aim to get a 
reduction of all instances of the vertex cover problem to an instance of the 
setcover problem. Given a graph $G(V, E)$, label all the edges with the elements 
of the universal set $X$. For each vertex contruct a set comprising the elements 
labelling the edges incident upon it. Finding a setcover in polynomial time would 
result in solution of the vertex cover problem in polynomial time, because the 
vertices corresponding to the subsets in the cover form the vertex cover. 
If any edge $e$ is not covered that means that the element labeling the edge is 
also not covered by the setcover and vice-versa.


6.3  This problem is similar to the previous problem except that the players 
represent the edges and packets are the vertices. For any vertex cover problem 
the previous reduction may be used to create an instance of the given problem.


(d)

6.4.  Any hamiltonian circuit problem in a $3$ degree regular graph may be reduced 
to an instance of a eularian cycle problem. Note that the necessary and sufficient 
condition for a graph to have an eularian cycle is that all vertices should be of 
even degree. In a $3$ degree regular graph, the maximal eularian subgraph covers 
all the vertices because the number of vertices is even and removing an edge from 
pairs of vertices gives an even degree graph. Also since all vertices are of 
degree $3$, the eularian cycle can enter and leave a vertex just once. Hence the 
solution to the maximal eularian sub-graph is the same as the hamiltonian cycle. 

6.5

(a)The low-degree spanning tree procedure may be called with $k=2$ to solve the 
hamiltonian path problem and  we know that the latter is not solvable in 
polynomial time.
  
(b) Find the highest degree vertex in the graph. From the adjacency list representation 
this is possible in $O(n^2)$ time. If the degree is at least $k$ then there is a 
such a spanning tree. The spanning tree may be constructed by assigning weight $1$ to k 
of the edges incident on the vertex and weight $2$ to the rest, and invoking Prim's or 
Kruskal's algorithm. 


(e) We can convert any graph into a regular graph by adding edges between vertices so 
that every vertex has the same degree. If the clique problem is not NPC for regular graph, 
we can find the cliques using polynomial time. Then we delete the edges we added 
from the cliques. Now we get the cliques for any graph. The adding edges and deleting 
edges run in polynomial time, because of the overall number of edges is polynomial. 
So the complexity of finding the clique for any graph is polynomial. It is obviously 
false. So the clique problem remains NPC for regular graphs.