Clique-problem for planar graph
Regarding the proof of the statement you quoted (to complement Juho's answer):

Let $G$ be a connected planar graph with $V &gt; 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 &gt; 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.