2
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ en.m.wikipedia.org/wiki/Wagner%27s_theorem $\endgroup$ Commented Jan 14, 2020 at 13:15
  • $\begingroup$ See also Robertson and Seymour $\endgroup$ Commented Jan 14, 2020 at 13:16
  • $\begingroup$ en.m.wikipedia.org/wiki/Graph_minor $\endgroup$ Commented Jan 14, 2020 at 13:22
  • $\begingroup$ 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"? $\endgroup$
    – Vakole
    Commented Jan 14, 2020 at 13:52

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.