Is K6 a planar graph?

Question

Using the condition $m\leq3n-6$, where $m$ equals the number of edges in the graph and $n$ is the number of vertices, I reasoned that for $K6$, the number of edges is $2\times 6 = 12$. With the vertices being equal to 6, $3n-6 = 12$. So $12\leq 12$, and the inequality condition is satisfied. So, is this reasoning correct to show that $K6$ is a planar graph?

Answer 1

Not even $K_5$ is planar, let alone $K_6$. There are two issues with your reasoning.

First, the complete graph $K_n$ has $\binom{n}{2}=\frac{n(n-1)}{2}$ edges. There are $(n$ choose $2)$ ways of choosing $2$ vertices out of $n$ to connect by an edge. As a result, for $K_5$ the equation $E\le 3V-6$ becomes $10\le9$, which is false. This proves $K_5$ is not planar.

Second, even if $K_5$ did satisfy the inequality, that wouldn't be enough. Planar graphs satisfy the inequality, but not all graphs that satisfy the inequality are planar. A counterexample is the bipartite graph $K_{3,3}$. In general, the complete bipartite graph $K_{m,n}$ has $m+n$ vertices and $mn$ edges, so the equation $E\le 3V-6$ for $K_{3,3}$ becomes $9\le12$. Nonetheless, you can prove $K_{3,3}$ is nonplanar using Euler's formula $V-E+F=2$; see here.

Kuratowski's theorem says a graph is planar if and only if no subgraph is homeomorphic (i.e. topologically equivalent) to $K_5$ or $K_{3,3}$, so these two "forbidden graphs" by themselves are the gatekeeper for all planar/nonplanar graphs.