Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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!
Regarding the proof of the statement you quoted (to complement Juho's answer):
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.
The idea is that in a planar graph, there are no cliques of size 5 or more (see Kuratowski's theorem).
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.
