# Clique-problem for planar graph

I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion

This follows already from Kuratowski's theorem: a clique is at most of size 4.

I've never heard of that theorem before and the exercise indicates to proof it with the fact, that the class of planar graphs is closed under sub graphs. Thank you for your help!

• en.m.wikipedia.org/wiki/Wagner%27s_theorem Commented Jan 14, 2020 at 13:15
• See also Robertson and Seymour Commented Jan 14, 2020 at 13:16
• en.m.wikipedia.org/wiki/Graph_minor Commented Jan 14, 2020 at 13:22
• Mhh, the links doesn't really help me. I don't know much abouth graphs and therefore don't understand such (in my point of view) complex things. Could you maybe explain it in 1-2 sentences? And where is the connection to "closed under sub graphs"? Commented Jan 14, 2020 at 13:52

Let $$G$$ be a connected planar graph with $$V > 2$$ vertices, $$E$$ edges and $$F$$ faces. We know from Euler's formula that $$V-E+F=2$$.
Now let us count the number $$q$$ of $$(e,f)$$ pairs where $$e$$ is an edge and $$f$$ is a face incident to $$e$$. Because every edge is incident to at most two faces, $$q \leq 2E$$. Because every face is incident to at least $$3$$ edges, $$q \geq 3F$$. Thus, $$3F \leq 2E$$. Using this together with Euler's formula we get that $$3V = 3E - 3F + 6 = E +6 + (2E - 3F) \geq E+6$$. Thus $$E \leq 3V-6$$.
Now, if some graph had a clique of size $$5$$, by taking this clique as a subgraph we would have that the complete graph on $$5$$ vertices $$K_5$$ is planar. But this graph has $$V=5$$ and $$E=10$$, thus $$E > 3V-6$$, which contradicts what we have just shown. Thus, $$K_5$$ is not planar and our original graph has no clique of size $$5$$ or more.
So suppose the problem is "is there a clique of size $$k$$ in a given planar graph $$G$$?" Now, if $$k \geq 5$$, we immediately answer NO. If $$k \leq 4$$, we can simply check every subset of the vertices of size $$k$$ (note that there are $$\Theta(n^k)$$ such subsets). If any one of them induces a $$k$$-clique, we answer YES. Otherwise, we answer NO. Hence, the problem is in P.