complete graph theory problem This may be a very trivial proof, but I was wondering if anyone could show/prove why you cannot have a PLANAR graph where every node is joined to at least 5 others.
 A: Suppose we have a planar graph, let $E,F,V$ be the number of edges faces and vertices.
Let $\mathcal F$ be the set of faces, notice that $\sum\limits_{f\in \mathcal F} |f|=2E$ because every edge is incident to two faces.
This implies that $2E\geq 3F\implies F\leq \frac{2E}{3}$, now use euler's formula:
We have $V-E+F=2\implies V-E+\frac{2E}{3}\geq 2\implies V-2\geq \frac{E}{3}\implies E\leq3V-6$
Notice that $K_5$ has $5$ vertices and more than $3\cdot5-6=9$ edges, so it is not planar.

Reading the comments, you seem to be wondering whether planar $5$-regular graphs exist, they do. For example you can consider the graph of the icosahedron.

A: In fact the result is slightly stronger - every complete graph $K_n$ with $n \ge 5$ is not planar - that is, cannot be drawn in the plane without edge crossings.
You can get this by examining the Euler relationship, $v-e+f=2$ that should hold for a graph that can be drawn in the plane, and considering that every face $f$ should be bounded by at least $3$ edges. So for $K_5$, $v=5, e=10$ and thus we expect $f=7$, which then require more than $10$ edges to delineate - so $K_5$ is not planar.
