Show that a graph with at least half of nodes of degree at least 10 is not planar.

Question

I am having troubles solving this exercise of a sample test:

G=(V, E) is a simple, connected, undirected graph with |V|=n and |E|=m and no bridge. Show that, if G has at least half of its vertices of degree at least 10, G is not planar.

I was thinking of using the m <= 3n-6 property, but still do not know where to go from there.

Edit: I have thought of something: we know that for every graph of |V|>=11, either itself or its complement is planar. Since in this exercise more than half of the vertices have a degree of at least 10, G is not planar, but its complement is. Can I somehow use this to prove it?

Answer 1

Suppose $G$ has no bridge and at least half its vertices of degree at least 10.

Since there is no cut-edge, every vertex has degree at least 2. With at least half the vertices having degree at least 10, and the remainder having degree at least 2, the average degree of $G$ is at least $(10 + 2)/2 = 6$.

Therefore $G$ has at least $6 n / 2 = 3n$ edges, so it cannot be planar.

Answer 2

This is true even removing the condition that $G$ is bridgeless.

Let $G$ be such a graph. Assume that $G$ is planar. We may assume that $G$ has no vertices of degree 1. [Indeed, let $v$ be a vertex of degree 1. Then the face $F$ that $v$ is in has at least 2 other vertices; add an edge between $v$ and any vertex in $F$ that $v$ is not already adjacent to; the resulting graph will still be simple and planar, have at least half of its vertices with degree 10 or greater, and have one less vertex of degree 1. Repeat this until there are no more degree-1 vertices left.]

Then that half of the vertices of $G$ have degree at least 10 and the remaining vertices have degree at least 2 imply that $G$ cannot be planar after all; too many edges as observed in the above answer by Nick Matteo.