2
$\begingroup$

Since $m \ge 3n-5$ and $n \ge 5$, I have a theorem which tells me that $G$ is not planar. It seems like a natural approach to do a proof by contradiction and arrive at the fact that $G$ must be planar. It seems easiest to do this with Kuratowksi's theorem. However I'm having troubles making any progress like this since I don't really know how many edges or vertices would be in the subgraph which is a subdivision of $K_5$ or $K_{3,3}$ (although I'm not sure I necessarily need to know that).

Any help or tips on a different approach would be greatly appreciated.

$\endgroup$
2
$\begingroup$

Assume the converse. Then the graph $G$ contains a vertex $v_1$ with degree at most $3$. Removing $v_1$ and edges incident to it from $G$ we obtain a graph with $n-1$ vertices and at least $3(n-1)-5$ edges which contains a vertex $v_2$ with degree at most $3$. Remove the vertex $v_2$ edges incident to it from the graph ... and so forth. We stop when there remains $4$ vertices, so we have removed $n-4$ vertices and at most $3(n-4)$ edges and the final graph has at most ${4 \choose 2}=6$ edges. Thus initially we had at most $6+3(n-4)<3n-5$ edges, a contradiction.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I figured there'd be an easy way to do it without planarity, thanks a bunch! $\endgroup$ – SenoritaChad Oct 30 '17 at 0:42
  • 1
    $\begingroup$ @ToanPham Thanks for the correction. $\endgroup$ – Alex Ravsky Oct 30 '17 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.