0
$\begingroup$

Suppose $G$ is a non planar graph such that $G/e$ is planar for every edge. then want to show that at most six vertices of $G$ have degree 3 or more.

Well I know that a G is non planar iff it contains a subdivision of $K_{5}$ or $K_{3,3}$ as a subgraph, also G itself must be this subgraph because if not it would contradict that $G/e$ is planar.

So is that enough of to make the conclusion?

$\endgroup$
  • $\begingroup$ If G was not the subgraph that contained a subdivision, but removing an edge made it planar, would be a contradiciton $\endgroup$ – PersonaA Feb 14 '17 at 19:18
  • 1
    $\begingroup$ you showed that $G$ is $K_{3,3}$ or $K_{5}$. That is not exactly true, since $G$ may also contain isolated nodes. This is sufficient to prove your thesis.. $\endgroup$ – Exodd Feb 14 '17 at 19:21
  • $\begingroup$ @Exodd Please explain what is meant by it is sufficient but also not true $\endgroup$ – PersonaA Feb 14 '17 at 19:21
0
$\begingroup$

Following your reasoning, $G$ must contain a subgraph $G'$ that is (a subdivision of) $K_{3,3}$ or $K_5$. If $G$ also contains an edge $e$ not in $G'$, then $G/e$ is not planar, that is an absurd.

This means that the edges of $G$ concide with the edges of $G'$, but the same is not true for the nodes. In fact $G$ may contain nodes of degree 0 that are not included in $G'$.

In any case, $G$ contains only 5 or 6 nodes with degree greater or equal than 3, that are the nodes in $G'$ (without conunting the ones in the subdivision that have degree 2), so the thesis is true.

$\endgroup$

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.