If the connectivity of a graph is $\geq 6$ then the graph is nonplanar

38 Views Asked by At

Show that if the connectivity $c$ of a graph is at least $6$ then the graph is nonplanar.

I know that $c \leq 2e/v$ (i.e. the connectivity is less than or equal to the average degree of a vertex), and that for planar connected graphs we have $e \leq 3v - 6$.

Proof: Suppose $G$ is planar. We know from a previous theorem and using the fact that $c \leq 6$ that $c \leq 2e/v \implies 3v \leq e$. We also know that $G$ is connected because $c \geq 6$, so we can use the fact that $e \leq 3v - 6$. Putting those two inequalities together, we have that $e \leq 3v - 6 \implies e\leq e - 6$, a contradiction. Therefore, $G$ is not planar.

I'm wondering how my proof looks, it seems too simple to be true...