# Connection between planar graph and vertex cover

I have two similar problems in which I'm trying to find a connection to help me solve one of them.

In the first one I'm given a graph G = (V,E) , integer k, and vertex cover U of size k. The objective is to find the largest clique (max size clique in G).

The second one is instead of a vertex cover, U is is a group of vertices that make so that G - U is planar graph.

What I'm searching for is to show that given any $$\epsilon > 0$$ the problem admits $$1+ \epsilon$$ approximate kernel of size linear in k.

When the input is as in the first problem and I get a vertex cover I successfully manage to show that, So my actual question is is there any relation between U being vertex cover and that removing U making the graph planar?

I know that the max size clique of the graph G[G-U] is at most 4, but I don't know if U has any cliques or maybe even U has vertices that with G-U create a bigger clique.

• What happens when your graph contains two disjoint cliques? Jul 13 at 8:11
• If both of them are of max size, it doesn't matter which of them you find Jul 13 at 8:17
• My point is. What happens when you remove one? The other one stays. Hence the graph is not planar (if the cliques are of size at least 5) Jul 13 at 9:19
• That's true (even if you have one clique of size at least 5 it's not planar), I'm just trying to find if I can make any conclusion that relate the two problems Jul 13 at 9:27