(computability and complexity): A vertex cover in an undirected graph G=(V,E) is a set of vertices U, so that every edge in E has at least one end in U.

We'll define the following function:f(G,v)=minimal vertex cover that v belongs to

the input is an undirected graph G and a vertex v of G.

The function returns an natural number, that is the smallest size of vertex cover in G that v belongs to

1)Prove: If it is possible to compute f in a polynomial time then P=NP

2)Prove: If it is possible to estimate function f in a constant +5 in polynomial time then P=NP (meaning: if it is possible to calcualte function g(G,v) in a polynomial time, and it is guarenteed that , then P=NP.

f(G,V) - 5